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

2020 KAKAO BLIND RECRUITMENT

 

Lv.2 문자열 유형

 

"ababcdcdababcdcd"의 경우 문자를 1개 단위로 자르면 전혀 압축되지 않지만, 2개 단위로 잘라서 압축한다면 "2ab2cd2ab2cd"로 표현할 수 있습니다.

다른 방법으로 8개 단위로 잘라서 압축한다면 "2ababcdcd"로 표현할 수 있으며, 이때가 가장 짧게 압축하여 표현할 수 있는 방법입니다.

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

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

 

 

풀이

 

문자열 압축이 가능할때 최소로 압축 할 수 있는 길이가 N//2 인 점이 키포인트이다.

또한 슬라이스를 늘려가면서 이중 루프로 현재와 비교 슬라이스에 조건을 만족하는지 카운트하여 min으로 최소 길이를 반환하면 된다.

 

이것 외에 좋은 풀이 방법은 없어보이나, 문자열 길이가 1000개 이하기 때문에 시간복잡도 최적화가 필요 없는 문제이다.

 

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

    if N <= 1:
        return N

    answer = N

    for x in range(1, N//2 + 1):
        res = ""
        cur = s[:x]
        cnt = 1
        
        for y in range(x, N, x):
            com = s[y: x+y]
            if cur == com: # 반복 되었을 경우
                cnt += 1
            else:
                if cnt == 1: # 압축이 안됬을 경우
                    res += cur
                else:
                    res += (cur + f'{cnt}')
                    cnt = 1
                cur = com
                
        if cnt == 1:
            res += cur
        else:
            res += (cur + f'{cnt}')

        answer = min(answer, len(res))

    return answer