[Implementation] 이코테 “문자열 압축” Python 풀이

문제

• 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다.
• 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데,
• 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다.
• 간단한 예로 "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는 알파벳 소문자로만 이루어져 있습니다.

입출력 예시

입출력 예에 대한 설명

• 출력 예 #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/courses/30/lessons/60057

def solution(s):

    # 주어진 문자열의 길이로 최소 압축 길이 초기화
    min_len = len(s)

    # 탐색 단위 수를 1부터 문자열 중간 길이까지 늘려가며 확인
    for unit in range(1, (len(s)//2)+1):

        # 결과 문자열
        result = ""    

        # 첫 탐색 단위
        previous = s[0:unit]

        # 동일한 탐색 단위의 개수
        count = 1

        # 탐색 인덱스를 탐색 단위만큼 증가시키며, 이전 탐색 단위와 비교
        for idx in range(unit, len(s), unit):

            # 현재 탐색 단위를 슬라이싱
            now = s[idx:idx+unit]

            # 현재 탐색 단위가 이전 탐색 단위와 같다면
            if (now == previous):
                count += 1
            # 현재 탐색 단위가 이전 탐색 단위와 다르다면
            else:
                if (count >= 2):
                    result += str(count) + previous
                else:
                    result += previous
                previous = now
                count = 1

        # 남아있는 문자열에 대해 처리
        if (count >= 2):
            result += str(count) + previous
        else:
            result += previous    

        # 탐색 단위별로 압축 문자열의 길이를 비교해, 최소 압축 문자열의 길이를 저장
        min_len = min(min_len, len(result))

    return min_len

참고

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