[Python] 문자열 압축 [프로그래머스 Level2]

프로그래머스, 2020 카카오 공채 코딩테스트 기출 - 문자열 압축 LV2

문제 바로가기

스택을 사용하는 완전탐색문제

압축할 문자열 s가 매개변수로 주어질 때 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return 하도록 solution 함수를 완성해주세요.

입출력 예
['a', 'a', 'b', 'b', 'a', 'c', 'c', 'c']
2a2ba3c ===> 7
문자열을 1개 단위로 잘라 압축했을 때 가장 짧습니다.

다른 예시
abcabcdede와 같은 경우, 문자를 2개 단위로 잘라서 압축하면 abcabc2de가 되지만, 3개 단위로 자른다면 2abcdede가 되어 3개 단위가 가장 짧은 압축 방법이 됩니다. 이때 3개 단위로 자르고 마지막에 남는 문자열은 그대로 붙여주면 됩니다

s				result
--------------------------------------
"aabbaccc"			7
"ababcdcdababcdcd"		9
"abcabcdede"			8
"abcabcabcabcdededededede"	14
"xababcdcdababcdcd"		17

풀이

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

    for size in range(1, len(s) // 2 + 1):
        count = 1
        compress = 0
        
        prev = s[:size]
        for i in range(size, len(s) + size, size):
            curr = s[i:i + size]
            if prev == curr:
                count += 1
            else:
                compress += size + len(str(count)) if 1 < count else len(prev)
                prev = curr
                count = 1
        answer = min(answer, compress)

    return answer