[python3] 443. String Compression

풀이 일자: 23.03.02

난이도: [Medium]

분류: [Two Pointer]

문제 내용

알파벳이 들어있는 배열이 주어졌을 때 이를 String으로 변환하는 문제이다. 연속되는 반복적인 알파벳을 각각 하나의 그룹으로 묶었을 때, 해당 그룹의 길이가 1이면 그대로 해당 알파벳을 넣고 1이상이면 해당 알파벳과 그 그룹의 길이를 넣는 문제이다. ( 만약 10이상이면 자리수별로 쪼개서 넣어야 한다.)

 

이에 대한 정보를 초기에 주어지는 chars라는 배열에 넣어 처리해야 하며 리턴값은 s의 길이가 된다.

 

즉, 예를 들어본다면

 chars = ["a","b","b","b","b","b","b","b","b","b","b","b","b"]

위의 배열이 있다고 가정하자. 이를 압축하는 기준에 따라 압축한다면,

우선 "a"는 하나밖에 없다. → 첫 번째 기준에 따라 s에 "a"를 그대로 추가한다.

 chars = ["a","b","b","b","b","b","b","b","b","b","b","b","b"]
 
 chars = ["a"]  # 현재까지 넣은 것
 s = "a"

 

"b"는 12개가 있다.

→ 두 번째 기준에 따라 s에 "b"를 추가하고 반복되는 횟수인 12를 추가해야 하는데 s에는 12를 그대로 추가하지만 chars에는  "1" "2"로 나눠서 저장해야 한다.

 chars = ["a","b","b","b","b","b","b","b","b","b","b","b","b"]
 
 chars = ["a","b","1","2"];
 s = "ab12"

 

 

문제 해결 흐름

1. 일단 문제에서 constants Space Complexity로 처리하라고 했기 때문에 배열같은 것을 사용하면 안되겠다.

→ chars 내부에서 in-place로 처리해야겠네.

 

2. 숫자를 세는데 문자가 1번만 나오는 경우 그대로 넣고 여러번 나오면 그 횟수를 chars에 넣어야한다.

→ in-place로 처리해야하니까 2개의 포인터를 사용해서 바꿔야겠다.

→ 1개의 포인터는 현재 문자와 횟수를 기록하는 위치를 의미/ 나머지 1개는 문자와 횟수를 탐색하는 위치를 의미

 

=> 채점을 돌려보면 실질적으로는 chars의 내용을 확인한다.. 즉 chars를 변환해주는 것도 중요하다.

 

class Solution:
    def compress(self, chars: List[str]) -> int:
        l = len(chars);
        ptr, cnt = 0, 0;
        prev = "";
        
        for i in range(l):
            if chars[i] == prev:
                cnt += 1;    
            else:
                prev = chars[i];
                if cnt > 1:
                    length = len(list(map(int, str(cnt))));
                    chars[ptr:ptr+length] = list(map(str, str(cnt)));
                    ptr += length
                chars[ptr] = prev;
                ptr += 1;
                cnt = 1;
        
        if cnt > 1:
            length = len(list(map(int, str(cnt))));
            chars[ptr:ptr+length] = list(map(str, str(cnt))); 
            ptr += length
        
        chars = chars[:ptr];
        print(chars);
        s = "".join(chars);

        return len(s);

 

=> 중복되는 코드가 존재한다. while문으로 바꾼다면 더 깔끔하게 처리 가능할 것이다.

 

 

Time Complexity: O(N)

chars 속의 문자와 횟수를 탐색하기 위해 다 돌아야 하기에 chars의 길이인 N이 시간복잡도가 된다.

 

Space Complexity: O(1)

주어진 배열 내에서 변경을 했고 몇 개의 변수만을 사용했기 때문에 O(1)의 공간복잡도를 가지게 된다.

 

다른 해결 방식(Official Solution)

class Solution:
    def compress(self, chars: List[str]) -> int:
        i = 0
        res = 0
        while i < len(chars): # 탐색이 끝날 때까지..
            group_length = 1
            while (i + group_length < len(chars)             #chars의 내부 문자가 연속적으로 이어지고
                   and chars[i + group_length] == chars[i]): #마지막에 도달할 때까지
                group_length += 1                            # 1을 증가
            chars[res] = chars[i]                            # 값을 넣는 포인터에 해당 문자를 넣고
            res += 1                                         # 해당 포인터를 증가시킴
            if group_length > 1:                             # 만약 연속적으로 이어진 횟수가 1을 넘으면
                str_repr = str(group_length)
                chars[res:res+len(str_repr)] = list(str_repr)
                res += len(str_repr)                         # str로 변환해 list로 넣고 그 크기만큼 해당 포인터를 증가
            i += group_length                                # group의 크기만큼 탐색 포인터를 증가
        return res

=> 내 풀이보다 훨씬 간결하고 깔끔하다.

 

Time Complexity: O(N)

chars 속의 문자와 횟수를 탐색하기 위해 다 돌아야 하기에 chars의 길이인 N이 시간복잡도가 된다.

 

Space Complexity: O(1)

주어진 배열 내에서 변경을 했고 몇 개의 변수만을 사용했기 때문에 O(1)의 공간복잡도를 가지게 된다.

 

 

문제 링크

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

String Compression - LeetCode