프로그래머스 문자열 압축(Python)

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

프로그래머스

드디어...! 오랜만에 저 스스로의 힘으로 레벨 2 문제를 풀어냈습니다!

저의 풀이

  문자열 s의 길이가 2 이하인 경우, 문자열 압축을 하던 안 하던 길이는 똑같습니다. 예를 들어 s == "a"인 경우, 딱 봐도 "a" 밖에 답이 없습니다. s == "aa"인 경우 "2a"로 압축되고, s == "ab"인 경우 "ab" 그대로이기 때문에 길이는 똑같습니다. 그래서 메인 로직에 들어가기 전에 문자열 길이가 2 이하인 경우 문자열 길이를 반환하도록 했습니다.

  이제 s의 길이가 3 이상인 경우를 생각해봅시다. 이 때부터는 묶는 단위(n)를 점점 늘려가며 압축을 해봐야 합니다. 묶는 단위는 문자열 길이의 절반까지만 키워도 충분합니다. 절반 이상으로 단위를 잡을 경우, 나머지 문자열의 길이가 단위보다 길이가 작으므로 압축이 되지 않습니다. 묶는 단위를 정한 후에는 0번째 인덱스부터 차례대로 비교하면서 압축을 진행해야 합니다. 압축 진행 중 나머지 확인해야 할 문자열의 길이가 묶는 단위보다 작은 경우, 나머지 문자열은 압축할 수 없다는 것이므로 나머지 문자열까지 같이 작성합니다.

  지금까지 얘기한 내용을 파이썬으로 작성한 코드가 아래의 코드입니다.

def solution(s):
    if len(s) <= 2:
        return len(s)
    else:
        answer = []
        n = 1
        while n <= len(s) // 2:
            compact_str = ""
            idx, cnt = 0, 1
            while idx <= len(s) - n:
                if s[idx : idx + n] == s[idx + n : min(idx + 2 * n, len(s))]:
                    cnt += 1
                else:
                    compact_str += (f"{s[idx:idx+n]}" if cnt == 1 else f"{cnt}{s[idx:idx+n]}")
                    if cnt > 1:
                        cnt = 1
                    
                    if n > len(s[idx + n : min(idx + 2 * n, len(s))]):
                        compact_str += f"{s[idx + n : min(idx + 2 * n, len(s))]}"
                idx += n
            answer.append(len(compact_str))
            n += 1
        return min(answer)

  프로그래머스 채점 결과 최대 12.97ms, 10.4MB 소모했습니다.