이코테-chapter12: 구현-문자열 압축

문제

풀이

• 문자열의 길이가 1000이하이기 때문에 가능한 모든 경우의 수를 탐색하는 완전 탐색을 수행할 수 있다.

코드

# https://programmers.co.kr/learn/courses/30/lessons/60057
# 난이도: 중, 메모리 제한: 128MB, 2020 kakao 신입 공채 기출

def solution(s: str) -> int:
    answer = len(s)

    # 1개 단위(step)부터 압축 단위를 늘려가며 확인
    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):
            # 이전 상태와 동일하다면 압축 횟수(count) 증가
            if prev == s[j:j+step]:
                count += 1
            # 다른 문자열이 나왔다면 (더 이상 압축하지 못하는 경우라면)
            else:
                compressed += str(count) + prev if count >= 2 else prev
                prev = s[j:j+step]  # 다시 상태 초기화
                count = 1
        # 남아 있는 문자열에 대해서 처리
        compressed += str(count) + prev if count >= 2 else prev
        # 만들어지는 압축 문자열이 가장 짧은 것이 정답
        answer = min(answer, len(compressed))

    return answer

if __name__ == '__main__':
    print(solution("aabbaccc"))  # 7
    print(solution("ababcdcdababcdcd"))  # 9
    print(solution("abcabcdede"))  # 8
    print(solution("abcabcabcabcdededededede"))  # 14
    print(solution("xababcdcdababcdcd"))  # 17

출처 & 깃허브

이것이 취업을 위한 코딩 테스트다 with python
github