문자열 압축

문제

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

문제 파악

주어진 문자열을 압축했을 때 가장 짧은 길이를 구하는 문제
예를 들어 "aabbaccc"는 "2a2ba3c"로 압축할 수 있음
이때, 압축 단위는 1~(문자열 길이 / 2) 까지 다양하게 시도하기

접근 방법

•	문자열을 1개, 2개, 3개… 단위로 잘라서 압축해보기
•	연속되는 문자열은 숫자+문자로 바꾸고, 그렇지 않으면 그대로 두기
•	모든 단위별 압축 결과 중에서 가장 짧은 길이를 찾기

문제 풀이

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 > 1 else prev
                prev = s[i:i+step]
                count = 1

        compressed += str(count) + prev if count > 1 else prev
        answer = min(answer, len(compressed))

    return answer