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

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

코딩테스트 연습 - 문자열 압축

 

제일 앞에서부터 정해진 길이로 잘라야 해서 입출력 예로 정해진 길이가 2라면

aa, bb

bb, ac

ac, cc 

의 경우만 비교해주면 된다.

 

cnt 로 중복된 문자열을 검사하여

예를 들면 정해진 길이가 1이고 'c' 에 대해서 cnt = 3 이므로 'ccc' 가 '3c' 가 된다. 즉, 길이가  i * cnt 에서 i + len(str(cnt)) 가 된다.

 

더 중복되지 않는 경우, 아래 temp 를 갱신시켜주고 cnt 를 다시 1로 설정한다.

 

s += ' ' 는 'ccc' 같은 경우 뒤에 오는 문자열이 없어 temp 에 영향을 미치지 않으므로 ' ' 를 추가하여 끝에 오는 중복되는 문자도 temp 값에 반영되도록 한다. 

 

def solution(s):
    answer = len(s)
    N = len(s) // 2
    s += ' '
    
    for i in range(1, N+1):
        j = 0
        cnt = 1
        temp = len(s) - 1
        
        while i+j < len(s):
            if s[j:i+j] == s[i+j:2*i+j]:
                cnt += 1
            else:
                if cnt > 1:
                    temp = temp - ((cnt - 1) * i) + len(str(cnt))
                    cnt = 1
                
            j += i

        answer = min(answer, temp)
        
    return answer

print(solution('aabbaccc')) # 7