이해

• 문자열을 압축하는 방법은 다음과 같다.
  • “aabbaccc”의 경우 “2a2ba3c”(문자가 반복되지 않아 한번만 나타나는 경우 1은 생략)와 같이 표현할 수 있다.
  • “ababcdcdababcdcd”의 경우 문자를 1개 단위로 자르면 전혀 압축되지 않지만, 2개 단위로 잘라서 압축하면 “2ab2cd2ab2cd”로 표현할 수 있다. 8개 단위로 잘라서 압축하면 “2ababcdcd”로 표현할 수 있으며, 이때가 가장 짧게 압축한 문자열이다.
• 문자열이 주어질 때, 가장 짧게 압축한 문자열의 길이를 return하라.

계획

• 문자열을 1개 단위부터 문자열 길이의 절반에 해당하는 단위까지 압축시켜 가장 짧게 압축된 문자열의 길이를 구해준다.
• 압축하는 과정은 while문을 사용하여 단위만큼 문자열을 건너 뛰면서 압축 횟수를 카운트해주어 압축 횟수가 2회 이상인 경우에 숫자를 문자열과 같이 붙여주는 방식으로 압축된 문자열을 구해준다.

실행

def solution(s):
    n = len(s)
    answer = n
    
    for c in range(1, n//2+1):
        compressed = ""
        i = 0
        j = i + c
        while i + c <= n:
            count = 1
            while j + c <= n and s[i:i+c] == s[j:j+c]:
                count += 1
                j += c
            if count > 1:
                compressed += str(count)
            compressed += s[i:i+c]
        
            i = j
            j += c
        if i < n:
            compressed += s[i:]
        answer = min(answer, len(compressed))
    return answer

개선

• 개선할 부분은 딱히 없는 것 같다.

회고

• 두 번째 푸는 문제라 쉬웠다.