[python] 프로그래머스 - 문자열 압축

https://programmers.co.kr/learn/courses/30/lessons/60057

코딩테스트 연습 - 문자열 압축

---

문제 풀이

입력 문자열의 길이가 최대 1000이었으므로 완전 탐색이 가능할 것으로 생각함. 따라서 망설임 없이 loop를 두 번 타는 걸 생각했다. → O(n^2) 풀이

압축률이 가장 높은 단위에서의 압축된 문자열의 길이를 반환해야 하기 때문에, 단위를 1부터 전체 문자열 길이까지 설정하고 각 단위에서 단위 문자열의 중복 개수를 찾아야 한다.

로직은 간단하므로, 문자열 중복 개수를 체크하는 것을 어떻게 구현하느냐가 중요하다. 중복 개수를 체크하기 위해서 실제 부분 문자열을 담고 있는 리스트를 사용했다. 실제로 압축된 문자열 또한 구현했다. (하지만 코드 수정을 통해 이런 부분은 생략 가능하고, 길이만으로도 판별이 가능하다)

코드

def solution(s):
    answer = len(s)
    
    # 완전 탐색
    for step in range(1, len(s)+1):
        compressed = ''
        arr = []
        
        for start in range(0, len(s), step):
            end = start + step
            sliced = s[start:end]

            if start == 0:
               arr.append(sliced)
                
            else:
                if arr[-1] != sliced: # 중복 문자열을 체크하는 것이기 때문에 0이어도 무관
                    if len(arr) == 1:
                        compressed += f'{arr[-1]}'
                    else:
                        compressed += f'{len(arr)}{arr[-1]}'
                    arr = [] # arr flushing
                
                arr.append(sliced)
        
        if arr: # 배열이 비어있지 않다면
            if len(arr) == 1:
                compressed += f'{arr[-1]}'
            else:
                compressed += f'{len(arr)}{arr[-1]}'
        
        answer = min([len(compressed), answer])
    
    return answer

 

arr에 들어가는 부분 문자열은 중복이 되지 않으면 flush되어야 한다. 또한 step이 달라질 때마다 flush 되어야 한다 (후자를 모르고 빼먹어서 compressed 결과가 이상하게 나왔었고 계속 틀렸었다). 하지만 위의 코드는 실제 arr에 물리적으로 문자열이 추가되고 비워지는 구조 + compressed가 실제로 존재하는 코드이기 때문에 문제 솔루션의 효율성 측면에서는 좋지 못하다. 또한 분기문이 너무 많아 코드가 복잡해보인다.

또한 outer loop에서 실제 문자열의 길이까지 탐색을 할 필요가 없다. 문자열 압축은 실제로 압축 단위가 문자열 길이의 반일 때까지만 유효하다. 부분 문자열 단위가 실제 문자열 길이의 반을 넘어가면 해당 문자열 내에서 중복이 될리가 없기 때문이다. 

실제로 "abcabc"라는 길이가 6인 문자열이 있다고 가정하면, 길이가 3인 부분 문자열 "abc"가 두 번씩 반복이 된다. 따라서 문자열은 "2abc"로 압축이 가능하다. 하지만, 문자열 뒤가 잘려서 "abcab"만 남는다고 하면 기존의 "abc"는 당연히 중복이 되지 않는다. 따라서, "abcab"의 경우에는 문자열 압축이 되지 않는다.

위의 문제점을 고려해서 풀이를 개선하면 다음과 같다.

# 효율성 개선 (outer loop range, arr, compressed를 int 변수로 바꿔서 길이만 판별)

def solution(s):
    answer = len(s)
    
    # 완전 탐색
    for step in range(1, len(s)//2+1):
        count = 1 # arr 길이를 확인하는 대신 count 변수 사용
        compressed = 0 # compress를 실제 문자열로 만드는 대신 길이만 담는 변수로 설정
        prev = s[:step]
        
        for start in range(step, len(s)+step, step):
          curr = s[start:start+step]
          if curr == prev:
            count += 1 # 배열에 문자열을 실제로 넣어주는 대신 count만 증가
          else:
            compressed += len(str(count)+prev) if count > 1 else len(prev)
            count = 1 # 배열을 비워주는 대신 count = 1로 리셋
            prev = curr
          
        answer = min(answer, compressed)

    return answer

---

정리

구현의 디테일이나 문제 풀이 효율성을 위해서 문제 요구 조건에 맞게 변수를 설정하는 것에 대해 생각해볼 수 있었다. 문제 설명을 통해서 압축 문자열 단위의 크기에 대한 상한값을 조금 더 디테일하게 생각해내지 못한 것이 아쉬웠고, 문제에서 필요한 게 뭔지 조금 더 깊게 생각하는 것이 필요하겠단 생각이 들었다. 문제가 heap & queue로 분류가 되어 있었는데 왜 그런지는 아직도 모르겠다...실제 이 문제를 풀면서 자료구조가 크게 중요하단 생각은 들지 않았다.