[프로그래머스/파이썬] 문자열 압축(60057) 풀이

---

• 프로그래머스 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 프로그래머스 코딩테스트 연습
• 문제 링크: 문자열 압축 (60057)
• 문제풀이 코드 GitHub 링크
• 풀이 언어: Python 3

풀이

문제

문자열을 일정 길이 단위로 잘라서, 연속으로 반복되는 토막은 개수 + 문자열 형태로 압축할 때 만들 수 있는 가장 짧은 길이를 구하는 문제입니다.

예를 들어 단위가 2라면 ababab은 3ab처럼 압축할 수 있습니다.

코드

def solution(s):
    answer = len(s)
    
    for d in range(1, len(s)//2+1):
        i = 0
        tmp = len(s)
        while i < len(s) - d:
            if s[i:i+d] == s[i+d:i+d*2]:
                cnt = 2
                i += d
                while i+d<len(s) and s[i:i+d] == s[i+d:i+d*2]:
                    cnt += 1
                    i += d
                tmp -= d * cnt - d - len(str(cnt))
            else: i += d
        answer = min(answer, tmp)
    
    return answer

설명

핵심은 가능한 단위 길이 d를 모두 시도해보는 것입니다.

• d = 1부터 len(s)//2까지 순회
• 같은 토막이 연속될 때 반복 횟수 cnt를 세고, 줄어든 길이를 계산
• 각 d에서 얻은 압축 길이 최솟값으로 전체 답 갱신

문자열 길이가 크지 않기 때문에 단위 길이 완전 탐색 + 선형 스캔으로 충분히 통과할 수 있습니다.

---

• 프로그래머스 문제풀이 전체 목록 보기

---