[프로그래머스] Lv2. 문자열 압축 (2020 카카오 공채)

🔗

풀이

우선 문자열의 최대 길이가 1,000이기 때문에 완전 탐색으로 비교해도 O(n^2) = 1,000 x 1,000 = 1백만이다.

1개짜리 단위부터 몇 개의 단위까지 자를 수 있는지를 먼저 고민해봐야 한다. 만약 길이가 14인 문자열이 있다고 가정하자. 그럼 7개까지는 앞의 7개와 뒤의 7개를 비교하는 게 가능할것이다. 하지만 8개로 자르게 되면 어차피 뒤의 문자는 6개이기 때문에 같을 수도 없다. 전체 문자열의 절반 이상의 길이가 되면 더 이상 비교하는 게 의미없어진다. 1개 이상부터 문자열 길이의 절반까지만 비교하면 된다.

i 단위로 문자를 반복적으로 자르면서 앞의 문자와 비교해서 개수를 누적하고, 앞과 뒤의 단위 문자열이 같다면 카운트를 1 증가시키고, 같지 않다면 현재까지 누적된 카운트와 문자를 저장하고, 카운트와 단위 문자열을 업데이트 한 후 비교를 이어나간다. 두 가지에 주의하면 된다.

• 반복되는 문자열이 하나만 나타난 경우 1은 생략한다
• 단위로 자르고 남는 부분은 붙여주면 된다.

def solution(s):
    min_length = len(s) # 현재 최소 길이
    
    for i in range(1, len(s)//2+1):
        char, cnt, j, ps = s[:i], 1, i, ''
        while j < len(s):
            if s[j:j+i] != char:
                if cnt == 1:
                    ps += char
                else: 
                    ps += f"{cnt}{char}"
                char, cnt = s[j:j+i], 0
            cnt += 1
            j += i
        
        ps += char if cnt == 1 else f"{cnt}{char}"
        if len(ps) < min_length:
            min_length = len(ps)
            
    return min_length