LeetCode - 443. String Compression (Python)

Medium - 문자열

Runtime : 3 ms / Memory : 18.13 MB

문제

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.

풀이

• 이 문제에서 유의해야 할 점은 uses only constant extra space로, 메모리 공간을 유의해야한다.

  • 물론 한국 기업의 경우, 코테에 mem 제한이 빡세진 않음

• r_idx 포인터의 경우, chars를 순회하면서 현재 값을 확인한다.

  • 같은 값이 계속 나온다면, 진행
  • 다른 값을 찾으면 멈추고 길이를 잰다.

• w_idx의 경우, chars 배열을 직접적으로 바꾼다.

  • 마지막 위치에 문자를 넣고, 그 이후에 계산된 수('6' or '12')를 길이에 맞게(1자리수 ,2자리수)로 넣는다.

class Solution:
    def compress(self, chars: List[str]) -> int:
        # using two pointer
        r_idx = 0
        w_idx = 0

        n = len(chars)

        while r_idx < n:
            cur = chars[r_idx]
            group_st_idx = r_idx # 현재 연속되는 문자열의 시작 위치

            while r_idx < n and chars[r_idx] == cur:
                r_idx += 1
            
            cnt = r_idx - group_st_idx
            chars[w_idx] = cur
            w_idx += 1
            if cnt > 1:
                for digit in str(cnt):  # 12일 경우, [1, 2]로 입력
                    chars[w_idx] = digit
                    w_idx += 1
        
        return w_idx