443. string compression

Given an array of characters chars, compress it using the following algorithm:

Begin with an empty string s. For each group of consecutive repeating characters in chars:

If the group's length is 1, append the character to s.
Otherwise, append the character followed by the group's length.
The compressed string s should not be returned separately, but instead, be stored in the input character array chars. Note that group lengths that are 10 or longer will be split into multiple characters in chars.

After you are done modifying the input array, return the new length of the array.

You must write an algorithm that uses only constant extra space.

Example 1:

Input: chars = ["a","a","b","b","c","c","c"]
Output: Return 6, and the first 6 characters of the input array should be: ["a","2","b","2","c","3"]
Explanation: The groups are "aa", "bb", and "ccc". This compresses to "a2b2c3".
Example 2:

Input: chars = ["a"]
Output: Return 1, and the first character of the input array should be: ["a"]
Explanation: The only group is "a", which remains uncompressed since it's a single character.
Example 3:

Input: chars = ["a","b","b","b","b","b","b","b","b","b","b","b","b"]
Output: Return 4, and the first 4 characters of the input array should be: ["a","b","1","2"].
Explanation: The groups are "a" and "bbbbbbbbbbbb". This compresses to "ab12".

처음에 아래처럼 이거 딕셔너리로 해야하나 싶어서 썼는데 되는 줄 알았는데 전혀 아니었다..

class Solution:
    def compress(self, chars: List[str]) -> int:
        dictoutput = {}

        for char in chars:
            if char not in dictoutput:
                dictoutput[char] = 0
            dictoutput[char] += 1

        compressed = len("".join(f'{k}{v}' for k, v in dictoutput.items()))

이건 결과는 내지만 3가지 문제가 있다.

1. compression 방식이 잘못됐다. 기존에 쓴 코드는 주어진 input 리스트에 있는 원소들을 세는 방식으로 해서 딕셔너리에 추가하는 방식이었는데, 문제에서는 consecutive한 문자들만을 compression하는 걸 요구했다. 즉, 내가 쓴 거는 각각의 문자들을 전역적으로 빈도를 계산해서 {"a":2, "b":2, "c":3}를 얻어내는 거지만, 사실 문제에서 제시하는 조건을 따르면 "a2b2c3"와 같은 방식으로 compress해야한다는 거다.
2. 문자들을 리턴하는 방식이 잘못됨. 문제에서는 compressed된 '리스트'의 길이를 리턴하라고 하고있지, '문자열'의 길이나 기존에 내가 쓴 코드와 같이 딕셔너리로 재구성한 다음에 전역적으로 문자들의 빈도수 계산하여 얻은 길이를 리턴하라고 하고있지 않다.

솔루션은 다음과 같다.

class Solution:
    def compress(self, chars: List[str]) -> int:
        write = 0  # Pointer to track where to write in chars
        read = 0   # Pointer to read through chars
        
        while read < len(chars):
            char = chars[read]  # Step 1
            count = 0
            
            # Step 2: Count the occurrences of the current character
            while read < len(chars) and chars[read] == char:
                read += 1
                count += 1
            
            # Step 3: Write the character to chars
            chars[write] = char
            write += 1
            
            # Step 4: Write the count to chars if greater than 1
            if count > 1:
                for digit in str(count):
                    chars[write] = digit
                    write += 1
        
        # Step 5: The length of the compressed list is the final value of write
        return write

최초에는 write와 read를 가리키는 두 개의 포인터를 선언해준다. 그 다음 while 루프를 이용해서 input 리스트 내 원소를 처음부터 쭉 읽어나가면서 더 이상 동일한 원소가 읽히지 않는다면 동일한 원소가 나온 것 만큼 숫자를 마지막으로 센 원소에다가 write하고 ([a, a, b, b, b] 이러면 [a, 2, b, b, b] 이런 식으로), 최종적으로 write를 가리키는 포인터의 포지션이 어디에 있는지를 갖고 리턴을 하는 거다.

참고로 while과 for-loop의 차이점을 다시 복기하자면, 전자는 특정한 몇 번을 진행하든지 간에 특정한 조건을 만족할 때까지 루프를 돌리는 거고, for는 어떤 객체가 주어졌을 때 거기에 있는 원소들의 갯수만큼 특정 조건에 맞게 루프를 돌리는 거다.