[LeetCode | Python] 443. String Compression

느낀점

투포인터를 알차게 잘 활용했던 문제로, 공간복잡도의 제약을 잘 고려하여 풀어야하는 문제이다. 뭔가 투 포인터라는 감은 잡히는데, 순간 세개의 포인터가 필요하려나 싶었다.

문제

https://leetcode.com/problems/string-compression/description/

 

문자 배열 chars가 주어졌을 때, 다음 알고리즘을 사용하여 배열을 압축하세요.

1. 빈 문자열 s로 시작합니다.
2. chars에서 연속적으로 반복되는 문자 그룹을 찾습니다.
3. 그룹 길이가 1이면 해당 문자를 s에 추가합니다.
4. 그룹 길이가 1보다 크면 해당 문자와 그룹 길이를 s에 추가합니다. (길이가 10 이상이면 여러 문자로 분리합니다.)
5. 압축된 문자열 s를 별도로 반환하지 않고, 입력 배열 chars에 직접 저장합니다.
6. 입력 배열을 수정한 후, 배열의 새로운 길이를 반환합니다.
7. 추가적인 공간 복잡도는 상수 공간만 사용해야 합니다.

풀이

각각 포인터 두개를 두고, 하나는 리스트의 앞부분을 순차적으로 수정해주는 포인터, 다른 하나는 얼마나 문자가 반복되는지 확인해주는 포인터이다. 이중 반복문 처럼 보이지만 각 포인터가 배열을 순차적으로 순회하며, 내부 루프들의 실행 횟수 또한 N에 비례하므로, 전체 알고리즘의 시간 복잡도는 O(N)이 되었다.

class Solution:
    def compress(self, chars: List[str]) -> int:
        start_pointer = 0
        last_pointer = 0

        while last_pointer < len(chars):
            curr_letter = chars[last_pointer]
            cnt = 0
            while last_pointer < len(chars) and curr_letter == chars[last_pointer]:
                cnt += 1
                last_pointer += 1
            chars[start_pointer] = curr_letter
            start_pointer += 1
            if cnt > 1:
                for c in str(cnt):
                    chars[start_pointer] = c
                    start_pointer += 1            

        return start_pointer

 

결과

• 공간복잡도: $$ O(N) $$
• 시간복잡도: $$ O(1) $$