[ProblemSolving] 프로그래머스 60057번 문자열 압축 문제풀이

모든 경우의 수를 탐색하여 정답을 도출하는 완전 탐색 유형의 문제이다. 다음은 문제를 풀 수 있는 사이트 링크이다.

 

프로그래머스 60057번 문제

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

길이가 n인 문자열을 입력받아 문자열 단위를 나누어서 같은 문자열이 몇 개씩 나왔는지 확인하는 문제이다. 여기서 중요한 점은 문자열 단위를 나눌 때 n//2+1 이상으로 나누면 같은 문자열이 나오지 않으므로 n//2+1까지의 문자열 단위에 대해서만 탐색을 시행하는 것이 좋다.

 

"aabbaccc"를 이용하여 설명해보겠다. 다음은 문자열 단위에 따라 결과값을 정리해둔 표이다. 노란색은 가장 작은 값을 가지고 있는 값이다.

 

압축한 문자열 중 가장 작은 값을 가지고 있는 것은 문자열을 1개로 나눴을 때의 값이며 7이다. 위의 과정을 코드로 작성하면 다음과 같다.

 

def solution(s):
    answer = len(s)
    
    for step in range(1, len(s)//2+1):
        compressed = ""
        prev = s[0:step]
        count = 1
        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
 
s = input()
print(solution(s))

 

참고 문헌 - 이것이 코딩테스트다 with python, 나동빈, 한빛미디어