[코딩테스트] 문자열 압축 (2020 Kakao) in Python

압축할 문자열 s가 매개변수로 주어질 때, 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return 하도록 solution 함수를 완성.

programmers.co.kr/learn/courses/30/lessons/60057

 

풀이는 프로그래머스 수업 내용을 바탕으로 구현했습니다.

 

문제 풀이

- 문자열을 자르는 단위 (step)는, 1개부터 문자열 길이 전체까지 된다 (technically (문자열 길이 // 2 +1) 까지!)

- 각 step마다 문자열을 검사하고 압축된 형태로 변환,

- 이전에 했던 압축 형식과 길이를 비교하여, 더 짧은 것을 answer에 저장

- 결국 완전탐색처럼 구현하면 되는 것이다.

 

파이썬 구현

def solution(s):
	answer = len(s) # 초기화 - worst case
    
    for step in (1, len(s)): # 문자열 자르는 단위
        result = '' # 각 단위때마다 압축된 형태
        count = 1 # 문자열 반복 횟수 담는 변수
        i = 0 # 인덱스
        prev = s[i:i+step]

        while i + step < len(s):
            i += step
            if prev == s[i:i+step]:
                count += 1
            else:
                result += str(count) + prev if count >= 2 else prev
                count = 1
                prev = s[i:i+step]
        result += str(count) + prev if count >=2 else prev # 남는 문자 처리
        
        answer = min(answer, len(result))
    
    return answer