압축할 문자열 s가 매개변수로 주어질 때, 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return 하도록 solution 함수를 완성해주세요.
입력 | 압축된 문자열 | 출력 |
---|---|---|
"aabbaccc" | "2a2ba3c" | 7 |
"ababcdcdababcdcd" | "2ababcdcd" | 9 |
# 문자열 text와 자를 단위 num을 받아서 압축된 문자열의 길이 반환
def compress(text, num):
compressed = ''
n = len(text)
length = n // num * num # 각 단위로 잘랐을때 고려해야할 문자열 길이
end = length - (2 * num)
cnt = 1 # 문자열이 반복되는 횟수를 저장
for i in range(0, end + 1, num):
# num 단위로 문자열이 같은지 검사
if text[i:i + num] == text[i + num:i + 2 * num]:
cnt += 1
# 마지막 단위일 경우
if i == end:
compressed += str(cnt) + text[i:i + num]
else:
if cnt == 1: cnt = ''
compressed += str(cnt) + text[i:i + num] # 압축된 문자열 업데이트
cnt = 1 # 횟수 초기화
# 마지막 단위일 경우
if i == end:
compressed += text[i + num:i + 2 * num]
# 남는 문자열을 더함
compressed += text[length:]
return len(compressed)
def solution(s):
answer = []
if len(s) == 1:
return 1
# 1부터 len(s)의 절반 단위까지 num을 늘려가면서 압축해본다
else:
return min([compress(s, num) for num in range(1, len(s) // 2 + 1)])
def compress(text, tok_len):
words = [text[i:i+tok_len] for i in range(0, len(text), tok_len)]
res = []
cur_word = words[0]
cur_cnt = 1
for a, b in zip(words, words[1:] + ['']):
if a == b:
cur_cnt += 1
else:
res.append([cur_word, cur_cnt])
cur_word = b
cur_cnt = 1
return sum(len(word) + (len(str(cnt)) if cnt > 1 else 0) for word, cnt in res)
def solution(text):
return min(compress(text, tok_len) for tok_len in list(range(1, int(len(text)/2) + 1)) + [len(text)])