[프로그래머스-파이썬] 연습문제(LV2) : 문자열 압축

<문제출처>

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

프로그래머스

 

<체크포인트>

시간	쉽게해결	1시간이내	1시간 이상 or 몇 일 걸림	솔루션 보고 해결
체감 난이도	하	중	상	최상
이해도	완벽히이해	다소 헷갈리는 부분있음	이해못함
덧붙일 말

 

압축했을 때 최소로 얻을 수 있는 압축문자열 길이는?

 

<고민 끄적끄적>

<완전탐색 및 구현>
문자열의 길이가 길지 않았기 때문에 모든 길이의 단위로 압축해보고 가장 최소가 되는 값을 구하였다. 즉 1개단위로 자르고, 2개 단위로 자르고... 자를 수 있는 최대인 n // 2 개 단위까지 모두 잘라본 후 가장 최소가 되는 길이를 구하였다.

 

 

최종코드

# 몇개가 연속적으로 존재하는지 리턴
def check(index, a):
    i = index
    cnt = 1
    while i + 1 < len(a) and a[i] == a[i+1]:
        cnt += 1
        i += 1
    return cnt
    

def solution(s):
    n = len(s)
    answer = n
    # i개 단위로 압축했을 때를 반복해서 구해본다.
    for i in range(1, n//2 + 1): #O(500)
        a = []
        ans = ''
        for j in range(0, n, i):
            if j + i >= n:
                a.append(s[j:])
            else:
                a.append(s[j:j+i])
            
        
        # 압축된 문자열로 변환
        index = 0
        while index < len(a):
            cnt = check(index, a)
            if cnt == 1:
                ans += a[index]
            else:
                ans += str(cnt) + a[index]
            
            index += cnt
        
        # 압축된 문자열 길이 최솟값을 갱신
        answer = min(answer, len(ans))
            
    return answer