[알고리즘] 문자열 압축 Python

문자열 압축 - 카카오 2020 코딩테스트 문제입니다

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

 

 

## 문제접근 방법

문자열은 1, 2, 3, .... , len(s) // 2 단위로 자를 수 있습니다

문자열을 자르는 단위를 unit이라는 변수로 두겠습니다

 

그리고 s의 길이는 1 이상 1,000 이하라는 문제 조건이 있습니다

그러면 s는 1~1000, unit은 1~500 입니다

따라서 최대 계산 횟수는 1000 * 500 = 500,000 번입니다

 

파이썬이 1초에 5천만번 ~ 1억번 정도 연산이 가능하므로 전체 탐색으로 이 문제를 풀 수 있습니다

 

문자열과 자를 문자열 단위를 받는 함수를 만들고 그 중에서 가장 최솟값을 찾는 방식으로 구현하였습니다

문제에 주어진 조건을 그대로 구현하였습니다

 

최초 구현했다가 예외가 터져서 확인해보았는데 문자열과 자를 문자열 단위가 배수가 아니어도 가능했습니다

예를들어 8글자를 3단위로 잘라도 됩니다. abcabcdede를 3글자씩 자르면 2abcdede가 됩니다

 

import math


def solution(string: str):
    result = len(string)

    for i in range(1, (len(string) // 2) + 1):
        compress_length = compress_string(string, i)
        if compress_length > 0:
            result = min(result, compress_length)

    return result


def compress_string(string: str, unit: int):
    compressed_string = ""

    previous_string = string[0:unit]
    repeat_count = 1

    sliced_chunk = math.ceil(len(string) / unit)  # 문자열을 unit 단위로 잘랐을 때 나오는 개수입니다
    for i in range(1, sliced_chunk + 1):  # range 포함 관계는 [ ) 입니다. 마지막 문자열도 처리하기 위해서 +1
        start = unit * i
        end = unit * (i + 1)
        sub_string = string[start:end]

        if previous_string == sub_string:
            repeat_count += 1
        else:
            if repeat_count >= 2:
                compressed_string += str(repeat_count)
            compressed_string += previous_string

            previous_string = sub_string
            repeat_count = 1

    return len(compressed_string)

 

 

## 문제를 풀고나서

- niche case들을 문제 풀면서 주석으로나 적으면서 풀면 나중에 테스트 케이스 만들 때 도움이 된다고 느꼈습니다

 

- (자주 헷갈리는 파이썬 지식) range 포함 관계는 [  ) 입니다

range(10)  # 0, 1, 2, ..., 8, 9

range(1, 10)  # 1, 2, ...., 8, 9

 

- (문자열 자를 때 기본적으로 알아야 하는 파이썬 지식) 아래의 그림이 머리 속에 그려지면 좋습니다

string[1:3]   # bc

string[:4]     # abcd

string[0:]     # abcd

string[2:]     # cd

string[:3]     # abc