[프로그래머스 Lv2] 파이썬 - 문자열 압축

프로그래머스 - 문자열 압축

# 조건

• 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다.
• 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다.
• 간단한 예로 "aabbaccc"의 경우 "2a2ba3c"(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 같이 표현할 수 있는데, 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점이 있습니다.
  • 예를 들면, "abcabcdede"와 같은 문자열은 전혀 압축되지 않습니다.
• "어피치"는 이러한 단점을 해결하기 위해 문자열을 1개 이상의 단위로 잘라서 압축하여 더 짧은 문자열로 표현할 수 있는지 방법을 찾아보려고 합니다.
  • 예를 들어, "ababcdcdababcdcd"의 경우 문자를 1개 단위로 자르면 전혀 압축되지 않지만, 2개 단위로 잘라서 압축한다면 "2ab2cd2ab2cd"로 표현할 수 있습니다.
  • 다른 방법으로 8개 단위로 잘라서 압축한다면 "2ababcdcd"로 표현할 수 있으며, 이때가 가장 짧게 압축하여 표현할 수 있는 방법입니다.
  • 다른 예로, "abcabcdede"와 같은 경우, 문자를 2개 단위로 잘라서 압축하면 "abcabc2de"가 되지만, 3개 단위로 자른다면 "2abcdede"가 되어 3개 단위가 가장 짧은 압축 방법이 됩니다.
  • 이 때 3개 단위로 자르고 마지막에 남는 문자열은 그대로 붙여주면 됩니다.
• 압축할 문자열 s가 매개변수로 주어질 때, 위에 설명한 방법으로 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return 하도록 solution 함수를 완성해주세요.

제한 사항

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

# 접근 방법

• 완전 탐색으로 풀어도 무방한 길이이다.
• 문자를 자를 수 있는 단위는 1개부터 주어지는 s의 길이까지 이므로, 첫 번째 반복문은 자를 수 있는 단위를 표시 해준다.
  • 이 때, temp 변수에는 첫 번째 자르는 단어를 미리 할당해준다.
• 이후 2번 째 반복문은 첫 번째 자른 개수 i 부터, 전체 길이에 i만큼 더해준 인덱스까지 i개씩 탐색해준다.
  • 전체 길이에 i만큼 더해준 후, 슬라이싱을 한다면 인덱스 에러를 해결할 수 있기 때문이다.
• 처음 저장 했던 temp와 현재 탐색 중인 단어가 같다면 cnt를 늘려주고,
  • 다르다면, cnt가 1이라면 temp를 더해주고 temp를 변경,
  • cnt가 1이 아니라면 개수와 함께 new_word에 더해준다.

def solution(s):
    answer = 0
    result= []
    for i in range(1, len(s)+1):
        new_word = ''
        cnt = 1
        temp = s[:i]
        for j in range(i, len(s)+i, i):

            if temp == s[j:j+i]:
                cnt += 1
            else:
                if cnt != 1:
                    new_word = new_word + str(cnt) + temp
                else:
                    new_word = new_word + temp

                temp = s[j:j+i]
                cnt = 1

        result.append(len(new_word))
    answer = min(result)
    return answer