Q09. 문자열 압축 (2020 카카오 기출)

코딩테스트 연습 - 문자열 압축 | 프로그래머스 (programmers.co.kr)

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

 

내가 혼자힘으로 풀 수 있는 몇 안되는 문제 중 하나.

문자열을 1부터 시작해서 k를 증가시켜가면서 다 압축해보고 길이를 재야한다.

핵심은 압축 알고리즘인데,

나는 이렇게했다.

1. 문자열에서 k길이만큼의 부분문자열을 따온다. part라고 지칭

2. 이전에 따왔던 문자열(save라고 지칭)과 part를 비교해서 같으면 count를 1증가시킨다. count는 몇 번 반복되는지 세는 변수.

3. save와 part가 다르면 str(count)+save를 정답에 추가하고 save=part로 바꾼다. count도 1로 초기화.

이때 만약 count가 1이면 save만 정답에 추가한다.

 

def compress(s, k):
    comp = ""
    save = ""
    i = 0
    count = 1
    while i < len(s):
        part = s[i:i+k]
        
        if save == part:
            count += 1
        elif count == 1:
            comp += save
            count = 1
            save = part
        else:
            comp += str(count) + save
            count = 1
            save = part
            
        i += k
        
    if count == 1:
        comp += save
    else:
        comp += str(count) + save
    
    return comp
        

def solution(s):
    answer = 9999999999
    for i in range(1, len(s)+1):
        c = compress(s, i)
        answer = min(answer, len(c))
    
    return answer