프로그래머스 - 문자열압축

문제설명

문자열 압축을 할 때 특정 사이즈로 문자열을 맨 앞부터 끝까지 토큰화 해 붙어있지만 반복되는 토큰은 앞에 숫자를 써주는 식으로 할 수 있다. 주어진 문자열에서 가장 압축을 짧게 했을 때의 길이는 무엇일까요?
(단,s의 길이는 1 이상 1,000 이하입니다.)

아이디어

토큰 사이즈를 1~1000까지 바꿔가며 압축 결과물(1회 생성 시 1000걸림)을 다 부르트포스 하는것도 괜찮을것같았다

주의할 점

1. 압축 결과물을 만들 때
   처음 일치하는 경우엔 숫자 자리가 생성되고
   두번째 이상 일치하는 경우엔 이미 생성된 숫자자리를 고친다(자리수가 달라질 수 있음)
2. 토큰사이즈가 맞아떨어지지 않아 생긴 나머지는 원본 그대로 붙인다.

코드

def solution(s):
    answer = 1000 #초기값은 무압축
    print("s길이 : ",len(s))
    for sz in range(1 ,len(s)+1):
        cur_ans = sz #0 ~ sz-1만큼
        succ = 1
        past_token = s[0:sz]
        #print(sz,"sz에 따른 첫 토큰", past_token)
        for i in range(1,len(s)//sz):#불완전 사이즈 토큰은 없음, 뒤토큰(현재)가 앞토큰과일치?
            token = s[i*sz:(i+1)*sz]
            if(token == past_token):
                succ+=1
                if(succ>2):#이미 숫자로서 한번 들어가있었음
                    cur_ans = cur_ans - len(str(succ-1))+len(str(succ))
                elif(succ==2):#처음으로 겹침
                    cur_ans = cur_ans+len(str(succ))
                #print("같은 토큰",i,",",i+sz-1,",", token,",",succ,",",cur_ans)
            else:
                succ = 1
                cur_ans +=sz
                #print("다른 토큰",i,",",i+sz-1,",", token,",",succ,",",cur_ans)
            past_token = token
        cur_ans+=len(s)%sz
        #print(sz," , ",cur_ans)
        answer = min(answer,cur_ans)
            
    return answer