[프로그래머스-Lv2] 문자열 압축 / Python

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

import sys

input = sys.stdin.readline

s = input().rstrip()


def solution(s):
    answer = len(s)
    for step in range(1, len(s) // 2 + 1):
        compressed = ""
        prev = s[0:step]
        count = 1
        for i in range(step, len(s), step):
            if prev == s[i : i + step]:
                count += 1
            else:
                compressed += str(count) + prev if count >= 2 else prev
                prev = s[i : i + step]
                count = 1
        compressed += str(count) + prev if count >= 2 else prev
        answer = min(answer, len(compressed))
    return answer


print(solution(s))

 

해설

최대 압축할 길이는 원래 문자열 길이의 절반이다. 그 길이는 step이다.

 

1. step별로 단어들을 비교한다. 현재 단어와 다음 단어가 같다면 count를 증가시킨다.

2. 현재 단어와 다음 단어가 다르다면 compressed에 count와 단어를 저장한다. count가 0이라면 단어만 저장한다. 추가적으로, 이제 비교할 단어는 다음 단어(prev[i:i+step])가 된다.

3. 한 번의 step 과정이 끝나면 나머지 문자열을 compressed에 저장하고 여태 구한 compreesed의 길이와 현재 구한 compressed의 길이를 비교하여 더 작은 길이의 compressed를 answer에 저장한다.