[알고리즘] 프로그래머스 - 문자열 압축

문제

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

프로그래머스

 

풀이

만약 문자열이 abc 라면 2개씩 나누는것부터는 의미가 없다. ababa 라면 3개씩 나누는것부턴 의미가 없다. 무조건 처음과 똑같은 문자열 길이가 나오기 때문이다. => 즉 최대  문자열 길이 // 2 만큼 씩 나눠서 확인하면 된다는 뜻! 

해당 아이디어를 바탕으로 큐에 문자열을 넣어주고 1부터 문자열길이 // 2 까지 for문을 돌면서 각 케이스마다 문자열이 얼마나 압축되는지 확인한다. 문자열을 앞에서부터 잘라서 이전에 나온 문자열과 같으면 result값만 올려주고, 다른 값이 나오면 지금까지 동일하다고 나온 아이들의 값을 현재 문자열에 넣어준다. 말로 표현하기 조금 힘든데... 코드를 보면 바로 이해가 될 거다...!

사실 코드가 좀 더러운데 ㅠ 귀차니즘으로 인해 더 줄이진 않았다....

 

코드

from collections import deque
def solution(s):
    s_len = len(s)
    answer = s_len
    n = s_len // 2
    
    for i in range(1,n+1):
        q = deque(list(s))
        cnt_s = ''
        cnt_word = ''
        result = 0
        while q:
            word = ''
            for _ in range(i):
                word += q.popleft()
                if not q:
                    break
                    
            if cnt_word == '':
                cnt_word = word
                result = 1
                
            elif cnt_word != '' and cnt_word == word:
                result += 1
                
            else:
                if result == 1:
                    cnt_s += cnt_word
                else:
                    cnt_s += (cnt_word + str(result))
                cnt_word = word
                result = 1
                
            if not q:
                if result == 1:
                    cnt_s += cnt_word
                else:
                    cnt_s += (cnt_word + str(result))

        answer = min(answer,len(cnt_s))
        
    return answer