[알고리즘] 문자열 압축 문제 풀이 (Python)

문제보기

풀이

완전 탐색으로 밖에 풀이가 떠오르지 않는다. 입력의 길이이 또한 1이상 1000이하로 완전 탐색으로 풀어도 문제없을 것 같다.
먼저 압축할 문자의 단위 만큼 비교할 문자열을 뽑아내고 다음 문자열의 단위 길이만큼 비교를 하고 같으면 카운트를 하고 다르다면 현재까지 카운트된 숫자와 비교중인 문자열을 저장해놓고 다음 단위만큼 비교할 문자열을 다시 뽑아내고 비교를 이어간다.
이렇게 1부터 전체 길이의 반만큼 단위를 늘려가며 단위마다 압축된 문자열의 길이를 비교해서 가장 작은 길이를 구한다.

코드

def solution(s):
    answer = len(s)
    if len(s) == 1: return 1

    for i in range(1, len(s)//2+1):
        result = ''
        prev = s[0:i]
        cnt = 1
        
        for j in range(i, len(s), i):
            if prev != s[j:j+i]:
                result += prev if cnt == 1 else str(cnt) + prev
                prev = s[j:j+i]
                cnt = 1
            else:
                cnt += 1
        result += prev if cnt == 1 else str(cnt) + prev
        answer = min(len(result), answer)
            
    return answer