문자열 압축(카카오) 문제풀이

문제 

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

프로그래머스

 

 

문제 접근 방식

주어진 문자열을 1개 이상의 단위로 잘라서 가장 짧은 압축 길이를 구하는 문제이다. 문자열을 압축하기 전에는 어떤 단위로 잘라야 최소가 되는지 알 수 없기 때문에 글자수를 조절해가면서 문자열을 압축해야하는 완전탐색 및 문자열 처리 관련 문제이다.  아래 처리과정처럼 진행되도록 코드를 구현하였다.

 

처리과정

1. 글자 단위 k를 +1하며 순회(문자열의 절반까지)
    1.1. k라는 단위로 더 이상 자를 수 없게 되면 아래 작업을 수행하고 while문 종료
        1.1. [기준 단어]의 개수가 1이상이면 숫자를 [압축 문자열]에 추가
        2.2. [기준 단어]를 [압축 문자열]에 추가
        2.3. [남은 문자열] 을 [압축 문자열]에 추가
    1.2. [다음 단어]가 [기준 단어]와 같다면 [기준 단어 개수] +1 
    1.3. [기준 단어]와 다르다면 
        1.3.1. [압축 문자열]에 [개수 & 기준 단어]  추가
        1.3.2. [기준 단어]를 [다음 단어]로 변경

 

시간 복잡도

단위를 문자열 길이의 절반 만큼 순회해야하며, 내부에서 문자열을 자르면서 끝까지 순회해야하기 때문에 O(n^2)의 시간이 걸린다. n의 최댓값이 1000이므로 시간 내에 동작한다.

 

코드

def solution(s):
    answer = n = len(s)

    # 1. 글자 단위 k를 +1하며 순회(문자열의 절반까지)
    for k in range(1, n // 2 + 1):
        standard = s[:k]
        i = k
        same = 1  # 기준 단어와 같은 단어 개수
        compressed = ""  # 압축 문자열

        while True:
            # 1.1. k라는 단위로 더 이상 자를 수 없게 되면 아래 작업을 수행하고 while문 종료
            if i + k > n:
                if same > 1: # [기준 단어]의 개수가 1이상이면 숫자를 [압축 문자열]에 추가
                    compressed += str(same)
                compressed += standard + s[i:] # [기준단어 + 남은 문자열] 추가
                break

            # 다음 단어를 자른다.
            next = s[i:i + k] # 1.2. [다음 단어]가 [기준 단어]와 같다면 [기준 단어 개수] +1
            if next == standard:
                same += 1
            else: # [기준 단어]와 다르다면 [압축 문자열]에 [개수 & 기준 단어] 추가
                if same > 1:
                    compressed += str(same)
                compressed += standard

                standard = next # [기준 단어]를 [다음 단어]로 변경
                same = 1
            i += k

        answer = min(answer, len(compressed))

    return answer

 

 

회고

마지막 부분 처리 시 이전 기준 단어와 남은 단어를 처리하는 부분에서 시간을 썼다. 
> 처음과 끝부분에 대한 처리를 정확히 파악할 필요가 있다.