[LeetCode 75] Medium - 443. String Compression ☆

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".

 

Constraints:

• 1 <= chars.length <= 2000
• chars[i] is a lowercase English letter, uppercase English letter, digit, or symbol.

 

이 문제는 주어진 문자 배열 chars를 **압축(compression)**하는 문제입니다. 반복되는 문자들을 그룹화하고, 그룹의 길이를 포함한 형태로 배열을 수정해야 합니다. 문제의 주요 포인트는 주어진 배열을 직접 수정해야 하며, 추가 공간 사용은 최소화해야 한다는 점입니다.

---

문제 조건

1. 반복되는 문자들을 그룹화하여 문자 + 길이 형태로 배열을 수정합니다:
   • 예: "aa" → "a2"
   • 길이가 1인 문자는 그대로 유지됩니다:
     • 예: "a" → "a"
   • 길이가 10 이상인 경우, 각 숫자를 따로 저장해야 합니다:
     • 예: "bbbbbbbbbbbb" → "b12".
2. 결과 문자열의 길이를 반환합니다.
3. 배열을 수정:
   • 결과를 새로운 배열로 반환하지 않고, 입력 배열 chars를 직접 수정합니다.
4. 제약:
   • 1 ≤ chars.length ≤ 2000: 배열의 길이는 최대 2000.
   • 각 문자는 소문자, 대문자, 숫자, 또는 심볼로 구성됩니다.

문제 풀이

알고리즘

1. 포인터 기반 배열 수정:
   • write 포인터: 수정된 배열을 저장하는 위치.
   • count 변수: 반복되는 문자의 개수를 세는 데 사용.
2. 배열 순회:
   • 같은 문자가 반복되면 count를 증가.
   • 다른 문자가 나오면:
     • 현재 문자를 write 위치에 저장.
     • 반복 길이(count > 1일 경우)를 write 위치에 추가.
     • 다음 문자를 처리하기 위해 count를 초기화.
3. 결과 반환:
   • 최종 write 포인터 값이 압축된 배열의 길이.

https://youtu.be/Vd-YX40Zz0Q?si=33rvTE2UXHaKfpRX

 

class Solution:
    def compress(self, chars: List[str]) -> int:
        # writing_idx: 압축된 결과를 저장할 위치를 가리키는 포인터
        # chars_idx: 현재 처리 중인 문자를 가리키는 포인터
        writing_idx = 0
        chars_idx = 0

        # chars 배열을 순회하여 압축 작업 수행
        while chars_idx < len(chars):
            # currChar: 현재 그룹에서 반복되는 문자를 저장
            currChar = chars[chars_idx]
            # currCount: 현재 문자의 반복 개수를 추적
            currCount = 0            

            # 현재 문자가 반복되는 동안 반복 개수 계산
            while chars_idx < len(chars) and chars[chars_idx] == currChar:
                currCount += 1
                chars_idx += 1

            # 현재 문자를 writing_idx 위치에 기록
            """
            이 부분이 두번째 while 문 위로가면, 동작은 제대로 하지만, 느려짐
            => 두번째 while 문은 
               현재 문자(currChar)가 연속으로 몇 번 반복되는지 세기 위해 필요하며
			   이 루프가 끝난 후에야 currCount 값이 정확히 결정되고, 
            => writing_idx를 갱신하는 역할:
               writing_idx는 압축된 결과를 저장할 위치를 가리킴
            => 따라서, 문자와 숫자를 정확히 저장하기 위해, 
               currCount 값이 결정된 이후에 currChar를 저장하는 것이 더 효율임
            """
            chars[writing_idx] = currChar
            writing_idx += 1

            # 반복 개수가 2 이상인 경우, 반복 횟수를 기록
            if currCount > 1:
                # currCount를 문자열로 변환하여 각 숫자를 기록
                cntStr = str(currCount)
                for j in range(len(cntStr)):
                    chars[writing_idx] = cntStr[j]
                    writing_idx += 1

        # 압축된 배열의 길이를 반환
        return writing_idx