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

문제

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

최대 길이가 1000이기 때문에, 완전 탐색이 가능해 완전 탐색으로 문제를 풀었다.

길이가 1부터 Input의 길이까지 앞에서부터 자르도록 해서, 가장 짧은 문자열을 찾았다.

O(n^2)

코드

def solution(s):
    answer = 100000
    if len(s) == 1:
        return 1
    for i in range(1, len(s)):
        j = 0
        cnt = 0
        before = s[j:i+j]
        tmp = ""
        while j + i <= len(s):
            if before == s[j:i+j]:
                cnt += 1
            else:
                if cnt != 1:
                    tmp += str(cnt)
                tmp += before
                cnt = 1
                before = s[j:i+j]
            j += i
        if cnt != 1:
            tmp += str(cnt)
        tmp += before
        if j + i > len(s):
            tmp += s[j:]
        
        answer = min(answer, len(tmp))
    return answer

"""
aabbacc -> 2a2ba3c
가장 짧게 압축할 수 있는 방법 리턴

길이 만큼 한 후, 앞에서부터 계속 체크
O(n^2)
"""