[python] 프로그래머스_문자열 압축 (완전 탐색)

문제

 

풀이

입력으로 주어지는 문자가 1000 이하이기 때문에 완전탐색을 수행할 수 있다. 길이가 N인 문자열이 입력되면 1부터 N/2 까지의 모든 수를 단위로 하여 문자열을 압축하는 모든 방법을 확인하고, 가장 짧게 압축되는 길이를 출력하면 된다. 구체적인 방법은 step 사이즈로 문자열을 잘라서 prev에 저장해두고, 다음 위치를 step 사이즈로 자르고 prev와 똑같은지 비교하면서 진행한다.

 

def solution(s):
    answer = len(s)
    # step을 1부터 문자열 길이 반까지 늘려가며 확인
    for step in range(1, len(s)//2 +1):
        compressed = ""
        prev = s[0:step]  # 앞에서 부터 step 만큼의 문자열 추출
        count = 1
        # step 크기 만큼 증가시키며 이전 문자열과 비교
        for j in range(step, len(s), step):
            if prev == s[j:j+step]:
                count += 1
            # 다른 문자열이 나오면
            else :
                if count >= 2:
                    compressed += str(count) + prev 
                else :
                    compressed += prev 
                prev = s[j:j+step]
                count = 1
        # 마지막 남은 문자열 처리
        if count >= 2:
            compressed += str(count) + prev 
        else :
            compressed += prev
        answer = min(answer, len(compressed))

    return answer