[programmers/py] 문자열 압축

문자열 압축

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

문제 설명

간단한 예로 "aabbaccc"의 경우 "2a2ba3c"(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 같이 표현할 수 있는데, 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점이 있습니다. 예를 들면, "abcabcdede"와 같은 문자열은 전혀 압축되지 않습니다. "어피치"는 이러한 단점을 해결하기 위해 문자열을 1개 이상의 단위로 잘라서 압축하여 더 짧은 문자열로 표현할 수 있는지 방법을 찾아보려고 합니다.

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

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

문자열은 제일 앞부터 정해진 길이만큼 잘라야 합니다.

풀이

문자열의 길이가 14라면 가장 잛은 경우는 2*문자열의 반으로 최대 반복 횟수는 문자열 길이 // 2임을 알 수 있습니다.

따라서 1~len(s)+1까지 반복을 진행하고 각 문자열 압축 단위에 따라 잘라진 문자열들은 str_list에 보관합니다.

str_list를 돌면서 답을 확인합니다.

def solution(s):
    if len(s) == 1 : return 1

    answer = len(s)

    for i in range(1, len(s)//2 + 1): # 반복 횟수
        str_list = [] # 단위로 보관
        for j in range(0, len(s), i):
            str_list.append(s[j: j+i])
        
        # ans = 압축된 문자열을 저장, n은 반복 횟수
        n, ans = 1, "" 
        comp = "" # 단위 문자
        for st in str_list:
            if st == comp : n += 1
            else :
                if n >= 2: ans += str(n)+comp
                else : ans += comp
                comp, n = st, 1
        else :
            if n >= 2: ans += str(n) + comp
            else : ans += comp

        answer = min(answer, len(ans))
    return answer