[TIL] 리스트 압축

문제

* 문제
문자 배열 chars를 압축합니다. 

새로 만들어질 문자열을 s라고 가정했을 때,
연속적으로 반복되는 각 문자 그룹에 대해 그룹의 길이가 1이면 해당 문자를 s에 추가하고, 
그렇지 않으면 해당 문자와 해당 그룹 길이를 각각 s에 추가합니다. 

**
문자열 s는 별도로 반환하지 않고 입력 문자 배열 chars에 저장해야 합니다. 
단, 함수의 반환값은 새 문자열의 길이(정수)를 반환합니다.
**

그룹의 길이가 10보다 길면 (2자리 이상이면) 분할하여 저장합니다. 

일정한 추가 공간만 사용하는 알고리즘을 작성해야 합니다.

* 예시
1. 
	입력 : ["a","a","b","b","c","c","c"] 
	변환된 문자열(chars) : ["a", "2", "b", "2", "c", "3"]
	출력 : 6
	설명 : 문자열 그룹은 "aa", "bb", "ccc" 이며, 그룹의 문자와 길이를 뒤에 붙입니다.

2. 
	입력 : ["a"]
	변환된 문자열(chars) : ["a"]
	출력 : 1
	설명 : 문자열 그룹은 "a"이며, 길이가 1이기에 길이를 문자열에 추가하지 않습니다.

3. 
	입력 : ["a","b","b","b","b","b","b","b","b","b","b","b","b"]
	변환된 문자열(chars) : ["a", "b", "1", "2"]
	출력 : 4
	설명 : 문자열 그룹은 "a", "bbbbbbbbbbbb"이며, "a" 그룹의 길이는 1이기에 길이를 문자열에 추가하지 않고,
				"b" 그룹은 12의 길이를 갖고 있기에 "1","2"로 나누어 추가합니다.

 

뭔가 접근하기가 쉬우면서도 꽤나 복잡한 문제였다.

class Solution {
  int compress(List<String> chars) {
  	List<String> s =[];
    Map<String,int> freq = {};
    for(String c in chars){
        freq[c] = (freq[c] ?? 0) + 1 ;
    }

    for(var entry in freq.entries){
        s.add(entry.key);
        if(entry.value>1 && entry.value <10){
            s.add(entry.value.toString());
        }else if(entry.value>=10){

        }
    }
    return chars.length;
  }
}

처음에는 이런 식으로 접근을 했는데
문제를 다시 읽어보니 기존 리스트를 덮어써야 하는 조건이 있었다.

또한 중복되지 않고 하나뿐일때는 숫자 입력을 생략해주고
중복된 숫자가 10 이상이면 숫자 하나하나 떼어서 "1","0"과 같이 리스트에 삽입해줘야 한다.

상당히 복잡하다.

class Solution {
  int compress(List<String> chars) {
    Map<String,int> freq = {};
    for(String c in chars){
        freq[c] = (freq[c] ?? 0) + 1 ;
    }
    chars.clear();
    for(var entry in freq.entries){
        chars.add(entry.key);
        if(entry.value>1 && entry.value <10){
            chars.add(entry.value.toString());
        }else if(entry.value>=10){
            String s =entry.value.toString();
            for(int i=0;i<s.length;i++){
                chars.add(s[i]);
            }
        }
    }
    return chars.length;
  }
}

그냥 리스트를 비우고 새로 써주는 방식으로 작성했는데 
올바른 접근이 아닌 것 같았다.

배열에서 비교를 하고 중복된 문자는 삭제하는 과정을 거친 후에
중복된 문자의 수를 그 문자의 뒤에 삽입해주면 될 것이라 생각했다.

그러나 아무리 생각해도 어떻게 짜야할지 모르겠어서
답안을 보고 해석하는 시간을 가졌다.

int compress(List<String> chars) {
  int index = 0; // Pointer for writing the compressed characters in place
  int i = 0;     // Pointer for iterating through chars

  while (i < chars.length) {
    String currentChar = chars[i];
    int count = 0;

    // Count the number of consecutive repeating characters
    while (i < chars.length && chars[i] == currentChar) {
      i++;
      count++;
    }

    // Write the character
    chars[index++] = currentChar;

    // If the count is more than 1, convert it to string and write each digit
    if (count > 1) {
      for (var c in count.toString().split('')) {
        chars[index++] = c;
      }
    }
  }

  // Trim the list to the new length
  chars.length = index;
  return index;
}