입출력 예에 대한 설명
입출력 예 #1
문자열을 1개 단위로 잘라 압축했을 때 가장 짧습니다.
입출력 예 #2
문자열을 8개 단위로 잘라 압축했을 때 가장 짧습니다.
입출력 예 #3
문자열을 3개 단위로 잘라 압축했을 때 가장 짧습니다.
입출력 예 #4
문자열을 2개 단위로 자르면 abcabcabcabc6de 가 됩니다.
문자열을 3개 단위로 자르면 4abcdededededede 가 됩니다.
문자열을 4개 단위로 자르면 abcabcabcabc3dede 가 됩니다.
문자열을 6개 단위로 자를 경우 2abcabc2dedede가 되며, 이때의 길이가 14로 가장 짧습니다.
입출력 예 #5
문자열은 제일 앞부터 정해진 길이만큼 잘라야 합니다.
따라서 주어진 문자열을 x / ababcdcd / ababcdcd 로 자르는 것은 불가능 합니다.
이 경우 어떻게 문자열을 잘라도 압축되지 않으므로 가장 짧은 길이는 17이 됩니다.
접근법
먼저 최대로 가질 수 있는 압축 크기는 전체 문자열 크기의 절반입니다. 즉, 문자 압축은 문자열의 길이가 1부터 문자열 전체 길이의 절반까지 반복해서 확인하면됩니다! 이중 반복문을 사용해서 접근하겠습니다. 첫 번째 반복문은 압축할 문자열의 길이에 대한 반복문이고, 두 번째 반복문은 압축할 문자열의 길이 만큼 자르며 반복되는 문자를 확인하여 압축시키는 부분입니다.
나의 코드
def solution(s):
if len(s) == 1 : return len(s)
for size in range(1,len(s)//2 + 1):
count = 0
pre_string= ""
for i in range(0,len(s) + 1,size):
if pre_string[-size:] == s[i:i+size]: count += 1
else:
if count > 1: pre_string += str(count) + s[i:i+size]
else: pre_string += s[i:i+size]
count = 1
if size == 1: min_size = len(pre_string)
else :
if min_size > len(pre_string):
min_size = len(pre_string)
return min_size
