[Python] 문자열 압축

허창원·2024년 3월 9일

알고리즘

문제 설명

[level 2] 문자열 압축 - 60057

문제 링크

성능 요약

메모리: 10.2 MB, 시간: 0.03 ms

구분

코딩테스트 연습 > 2020 KAKAO BLIND RECRUITMENT

채점결과

정확성: 100.0
합계: 100.0 / 100.0

제출 일자

2024년 03월 09일 15:47:27

문제 설명

데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다.
간단한 예로 "aabbaccc"의 경우 "2a2ba3c"(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 같이 표현할 수 있는데, 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점이 있습니다. 예를 들면, "abcabcdede"와 같은 문자열은 전혀 압축되지 않습니다. "어피치"는 이러한 단점을 해결하기 위해 문자열을 1개 이상의 단위로 잘라서 압축하여 더 짧은 문자열로 표현할 수 있는지 방법을 찾아보려고 합니다.

예를 들어, "ababcdcdababcdcd"의 경우 문자를 1개 단위로 자르면 전혀 압축되지 않지만, 2개 단위로 잘라서 압축한다면 "2ab2cd2ab2cd"로 표현할 수 있습니다. 다른 방법으로 8개 단위로 잘라서 압축한다면 "2ababcdcd"로 표현할 수 있으며, 이때가 가장 짧게 압축하여 표현할 수 있는 방법입니다.

다른 예로, "abcabcdede"와 같은 경우, 문자를 2개 단위로 잘라서 압축하면 "abcabc2de"가 되지만, 3개 단위로 자른다면 "2abcdede"가 되어 3개 단위가 가장 짧은 압축 방법이 됩니다. 이때 3개 단위로 자르고 마지막에 남는 문자열은 그대로 붙여주면 됩니다.

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

제한사항

s의 길이는 1 이상 1,000 이하입니다.
s는 알파벳 소문자로만 이루어져 있습니다.

입출력 예

s	result
`"aabbaccc"`	7
`"ababcdcdababcdcd"`	9
`"abcabcdede"`	8
`"abcabcabcabcdededededede"`	14
`"xababcdcdababcdcd"`	17

입출력 예에 대한 설명

입출력 예 #1

문자열을 1개 단위로 잘라 압축했을 때 가장 짧습니다.

입출력 예 #2

문자열을 8개 단위로 잘라 압축했을 때 가장 짧습니다.

입출력 예 #3

문자열을 3개 단위로 잘라 압축했을 때 가장 짧습니다.

입출력 예 #4

문자열을 2개 단위로 자르면 "abcabcabcabc6de" 가 됩니다.
문자열을 3개 단위로 자르면 "4abcdededededede" 가 됩니다.
문자열을 4개 단위로 자르면 "abcabcabcabc3dede" 가 됩니다.
문자열을 6개 단위로 자를 경우 "2abcabc2dedede"가 되며, 이때의 길이가 14로 가장 짧습니다.

입출력 예 #5

문자열은 제일 앞부터 정해진 길이만큼 잘라야 합니다.
따라서 주어진 문자열을 x / ababcdcd / ababcdcd 로 자르는 것은 불가능 합니다.
이 경우 어떻게 문자열을 잘라도 압축되지 않으므로 가장 짧은 길이는 17이 됩니다.

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges

문제 풀이

def string_to_list_by_slice(s, num):
    rlist = []
    quotient = len(s) // num
    remainder = len(s) % num
    for i in range(1, quotient + 1):
        rlist.append(s[num * (i - 1) : num * i])

    if remainder:
        rlist.append(s[len(s) - remainder :])

    return rlist


def solution(s):
    # 1씩 증가하면서 문자를 잘라본다.
    # 자른 문자열을 앞뒤로 비교한다.
    # 비교했을때 같은 수만큼 숫자를 써준다.
    # 전체 문자열의 길이를 return한다.
    # 인덱스 증가폭을 활용한다면?
    # 일단 앞뒤 문자가 같을 때, 숫자를 생략하는 알고리즘 만들기
    # 마지막 3c 를 어떻게 추가할 것인가?
    answer = []
    for i in range(1, len(s) + 1):
        string_list = string_to_list_by_slice(s, i)
        count = 1
        result = ""
        for index in range(1, len(string_list)):
            if string_list[index - 1] == string_list[index]:
                count += 1
            else:
                if count == 1:
                    result += string_list[index - 1]
                    count = 1
                else:
                    result += str(count) + string_list[index - 1]
                    count = 1
        if count == 1:
            result += string_list[-1]
        else:
            result += str(count) + string_list[-1]
        answer.append(len(result))
    return min(answer)

이 문제에서 작성해야하는 코드는 2가지이다.
1. 문자열을 자르기
2. 잘려진 문자열을 압축하기

하지만 이 코드에서의 문제점은 문자열을 자를때, 1부터 len(s)까지 모두 자르는 것은 비효율적이다. 문자열은 절반을 잘랐을 때 최대로 압축될 수 있기 때문에 절반을 넘어서면 압축될 가능성이 없다. 그래서 이런 부분을 수정해야한다. 또, 나는 문자열을 리스트로 만들어서 잘라내는 코드를 작성했다. 하지만 이는 메모리를 낭비하는 코드이다.
문자열을 자르는 함수(string_to_list_by_slice)와 문자열 압축 함수(solution)을 작성했다. 이상으로 작성한 코드의 문제점을 발견하였다. 결과적으로 이 풀이를 개선할 수 있는 방법이 3가지가 있다.

개선방안

함수 분할: 코드의 가독성과 재사용성을 높이기 위해, 주어진 문자열을 주어진 길이의 단위로 잘라 압축하는 과정을 별도의 함수로 분리합니다.
중복 최소화: 이전 문자열과 현재 문자열이 같은 경우에만 카운터를 증가시키고, 다를 경우에는 압축된 문자열을 생성하는 로직을 단순화합니다.
리스트 사용 최소화: 문자열을 처리할 때 리스트 대신 문자열을 직접 조작하여 불필요한 메모리 사용을 줄입니다.

아래는 개선 방안을 적용한 코드이다.

def compress(s, step):
    compressed = ""
    prev = s[:step]  # 첫 번째로 잘라낸 문자열을 초기 비교 대상으로 설정
    count = 1
    for i in range(step, len(s), step):
        # 현재 스텝에서 잘라낸 문자열
        cur = s[i:i+step]
        if cur == prev:  # 이전 문자열과 동일하면 카운트 증가
            count += 1
        else:
            compressed += (str(count) + prev) if count > 1 else prev
            prev = cur  # 다음 비교를 위해 현재 문자열을 이전 문자열로 설정
            count = 1  # 카운트 초기화
    # 마지막에 처리되지 않은 문자열 추가
    compressed += (str(count) + prev) if count > 1 else prev
    return len(compressed)

def solution(s):
    answer = len(s)  # 최소 길이를 원래 문자열의 길이로 초기 설정
    for step in range(1, len(s) // 2 + 1):  # 문자열을 1개 단위부터 절반 길이까지 잘라보며 최소 길이 탐색
        compressed_length = compress(s, step)
        answer = min(answer, compressed_length)
    return answer

배운점

for i in range(step, len(s), step): 이 코드에서 len(s) = 24, step = 5라고 가정하면 i는 20까지 작동한다. 그리고 for문이 끝나서 마지막에 처리되지 않은 문자열 추가 코드를 작성하는 것이 필요했다. 항상 for i in range(a,b)로만 사용하여 3가지 변수를 쓰는 것에 미숙했는데 이번 기회에 어떻게 작동하는지 이해할 수 있었다.
또, 이전과 현재를 비교하는 알고리즘이 자주 등장하는데 prev를 초기값으로 설정해주고 현재 부분을 for문 내에서 작성하여 비교하는 코드를 작성하고 cur를 prev로 다시 설정해주는 방법을 기억해두어야겠다.