Programmers / 문자열 압축

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

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

 

문제를 이해하는 과정에서 오류가 있었다.

최대한 압축하면 되는 문제이지만, 정해진 방식으로만 압축이 이루어져야하는 문제였다.

 

예를 들어, abcabcdede의 경우

2개로 나눌 때, ab ca bc de de 이렇게 나뉘어져서 abcabc2de가 나오는 것이다.

3개로 나눌 때, 2abcdede가 된다. de가 중복되어 나오지만 3개씩 단어를 나누어야하기에 압축되지 않는 것이다.

 

처음에 중복되는 것은 모두 압축한 경우의 최소를 return하는 문제로 착각해서 오래걸렸다..

(이렇게 되면, 2abc2de 이렇게 나와야한다)

 

아무튼, 이정도로 어려운 문제가 아니었다고 한다~

풀이는 아래와 같다.

 

 

Solution 

def solution(s):
    result=[]
    if len(s)==1: # 한글자인 경우
        return 1

    for i in range(1,len(s)//2+1): #최대 반복 길이 = 문자열/2
        char = ''
        prev = s[:i]
        cnt = 1

        # i만큼씩 나눠서 동일한지 확인. 첫단어부터 시작해서 나누는 게 중요.
        for j in range(i,len(s), i):
            if prev == s[j:j+i]: # 다음 단어가 이전 단어와 동일한 경우
                cnt+=1
            else :  # 이전 단어랑 다른 경우
                if cnt!=1:  # 여러개 쌓여 있던 경우
                    char=char+str(cnt)+prev
                else:   # 이전 단어가 안 쌓여 있던 경우
                    char=char+prev
                prev=s[j:j+i]   # 이전 단어 변경해주기
                cnt=1   # 카운트도 갱신

        # 나머지 단어 처리
        if cnt != 1:
            char = char + str(cnt) + prev
        else:
            char = char + prev

        result.append(len(char))

    return min(result) # 가장 짧은 단어 길이 return