리트코드 - 443. String Compression

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

String Compression - LeetCode

 

문자 배열이 주어지면 다음 알고리즘을 사용하여 압축한다:
빈 문자열 s로 시작하여 연속적으로 반복되는 각 문자 그룹에 대해 문자 배열을 압축한다.

1. 그룹의 길이가 1이면 해당 문자를 s에 추가한다.
2. 그렇지 않으면 문자 뒤에 그룹의 길이를 추가한다.

압축 문자열 s는 별도로 반환하지 않고 입력 문자 배열 문자에 저장해야 한다. 그룹 길이가 10보다 길면 문자 배열에서 여러 문자로 분할된다는 점을 유의해야 한다.
입력 배열 수정을 완료한 후 배열의 새 길이를 반환한다.
일정한 추가 공간만 사용하는 알고리즘을 작성해야 한다.

 

풀이

투포인터를 활용한 풀이.

단순히 압축 문자열의 길이만을 반환하는 것이 아니라 문자 배열을 변환까지 함께 시켜야한다.

read 포인터를 활용해서 문자열이 바뀌기 전까지, 확인한다. 이후 해당 문자열의 개수를 문자열로 변환시켜서 이를 문자 배열을 변환시키는데 활용한다. 이때 활용하는 것이 write 포인터이다. 

맨 처음에 read 포인터와 write포인터를 일치시킨 후, 이후 해당 문자열의 개수를 문자배열에 입력할 때 write 포인터를 활용한다.

이를 통해 문자 배열을 효율적으로 변환시킬 수 있다.

 

class Solution:
    def compress(self, chars: List[str]) -> int:
        read = write = 0 # O(1)

        while read < len(chars): # O(n)
            chars[write] = chars[read] # O(1)
            count = 0 # O(1)

            while read < len(chars) and chars[read] == chars[write]: # O(n)
                read += 1 # O(1)
                count += 1 # O(1)
            
            if count > 1: # O(1)
                for c in str(count): # O(count)
                    write += 1 # O(1)
                    chars[write] = c # O(1)
            
            write += 1 # O(1)
        
        return write

 

while read < len(chars): 과 while read < len(chars) and chars[read] == chars[write]: 모두 시간 복잡도가 O(n)이기 때문에 이중 순환이라고 생각할 수 있지만 while read < len(chars) and chars[read] == chars[write]: 은 최악의 경우 문자 배열을 모두 순회하므로 O(n)이 되는 것이고, 한 번 순회하게 될 경우 while 문을 벗어나기 때문에 결국 종합적인 시간 복잡도는 O(n)이 된다.

 

공간복잡도는 추가적인 배열을 생성하지 않고 문자 배열을 변환하고 인덱스를 보관하기 위한 정수 배열만 선언하기 때문에 추가 공간 복잡도는 O(1)이다.