문제 설명
문자열을 1개 이상의 단위로 잘라서 압축하여 더 짧은 문자열로 표현할 수 있는지 방법을 찾아보려고 합니다.
예를 들어, "ababcdcdababcdcd"의 경우 문자를 1개 단위로 자르면 전혀 압축되지 않지만, 2개 단위로 잘라서 압축한다면 "2ab2cd2ab2cd"로 표현할 수 있습니다. 다른 방법으로 8개 단위로 잘라서 압축한다면 "2ababcdcd"로 표현할 수 있으며, 이때가 가장 짧게 압축하여 표현할 수 있는 방법입니다.
압축할 문자열 s가 매개변수로 주어질 때, 위에 설명한 방법으로 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return 하도록 solution 함수를 완성해주세요.
<예시>
"aabbaccc"
7
"ababcdcdababcdcd"
9
"abcabcdede"
8
"abcabcabcabcdededededede"
14
"xababcdcdababcdcd"
17
나의 풀이
모든 단위를 다 계산해보면서 가장 짧은 문자열을 찾을텐데,
먼저 생각해볼 문제
1. 단위는 몇까지 계산?
-> 문자열 s의 길이의 반 까지만. 반 이상의 slicing은 의미가 없다.
2. 각 단위마다 문자열은 얼마로 줄어드는가?
-> len(s) - (countOfUnit - 1) * unit + str(countOfUnit)
3. 어떻게 구현할 것인가?
# 길이 자체만 구해보기
def solution(s):
answer = len(s)
new_answer = len(s)
for unit in range(1, len(s) // 2 + 1):
cnt = 1
temp = 0
while temp < len(s):
if s[temp:temp + unit] == s[temp + unit:temp + unit +unit]:
cnt += 1
temp += unit
continue
temp += unit
if cnt > 1:
if cnt < 10:
new_answer = new_answer - (cnt-1)*unit + 1
else if cnt >= 10 ans cnt < 100:
new_answer = new_answer - (cnt-1)*unit + 2
else if cnt >= 100 and cnt < 1000:
new_answer = new_answer - (cnt-1)*unit + 3
else: # cnt == 1000
new_answer = new_answer - (cnt-1)*unit + 4
cnt = 1
answer = min(answer, new_answer)
new_answer = len(s)
return answer# 문자열도 같이 구해보기
def solution(s):
answer = s
new_s =""
for unit in range(1, len(s) // 2 + 1):
cnt = 1 # 문자열이 반복되는 횟수. 기본 1
temp = 0 # unit 단위 slicing 위한 변수
while temp < len(s):
if s[temp : temp + unit] == s[temp + unit : temp + unit + unit]:
cnt += 1
temp += unit
continue
if cnt == 1:
new_s = new_s + s[temp : temp + unit]
if cnt > 1:
new_s = new_s + str(cnt) + s[temp:temp + unit]
cnt = 1
temp += unit
if len(new_s) <= len(answer):
answer = new_s
new_s = ''
return len(answer)책 풀이
def solution(s):
answer = len(s)
for step in range(1, len(s) // 2 + 1):
compressed = ""
prev = s[0:step]
count = 1
for j in range(step, len(s), step):
if prev == s[j:j + step]:
count += 1
else:
compressed += str(count) + prev if count >= 2 else prev
prev = s[j:j + step]
count = 1
compressed += str(count) + prev if count >= 2 else prev
answer = min(answer, len(compressed))
return answer느낀 점
책 풀이가 훨씬 효율적이고 간결하다.
처음에 반복 단위가 '10'이 넘어가는 경우를 생각하지 못해서 애먹었다. 9a는 길이가 2 이지만 10a는 길이가 3 이니까.
slicing 에서도 고민을 많이 했는데, 내 풀이처럼 저렇게 복잡하게 하는 것보다 책 풀이처럼 range 함수를 잘 쓰면 되는 거였다.
for i in range(0, 100, 2) # 0, 2, 4, ..., 98난잡한 내 풀이에서도 배울 점이 있었는데,
if s[temp : temp + unit] == s[temp + unit : temp + unit + unit]:에서 왜 index 에러가 나지 않았을까? 마지막에는 분명히 범위를 벗어나는데...
문자열 len(s) = 10일 때, print(s[11:15])를 실행해보면,
에러가 나지 않고 그냥 아무것도 안 찍힐 뿐이다. type은 str이며, 값은 그저 "" 이다.
문자열 slicing은 index error에서 좀 유연한 편인 것 같다. 신기하지?
