Lv2. 문자열 압축
문자열을 1개 이상의 단위로 잘라서 압축하여 더 짧은 문자열로 표현할 수 있는지 방법
"ababcdcdababcdcd"의 경우 "2ab2cd2ab2cd", "2ababcdcd"로 표현 가능
표현한 문자열 중 가장 짧은 것의 길이를 리턴
계획 1
s="aabbaccc"="2a2ba3c" : 7
Convoltion에서 착안 filtering+sliding
step=1
conv = (a,a)(a,b)(b,b)(b,a)(a,c)(c,c)(c,c)
같은 거 (a,a)(b,b)(c,c)(c,c) : len(conv)=4
중복되는 것 체크 (c,c)(c,c) : cnt=1
answer = len(s)-len(conv)*step+(len(conv)-cnt)=8-4*1+(4-1)=7
step=2
(aa,bb)(ab,ba)(bb,ac)(ba,cc)
같은 거 len(conv)=0
answer = 8
...
min(answer)=7
def solution(s):
answer = []
for step in range(1, len(s) + 1):
conv = [(s[j * step:j * step + step], s[j * step + step:j * step + 2 * step])
for j in range(int(len(s) / step) - 1)
if s[j * step:j * step + step] == s[j * step + step:j * step + 2 * step]]
cnt = 0
for x, y in zip(conv, conv[1:]):
if x == y:
cnt += 1
answer.append(len(s) - len(conv) * step + (len(conv) - cnt))
return min(answer)
문제점
s="aaccaccc"="2a2ca3c" : 7
(a,a)(a,c)(c,c)(c,a)(a,c)(c,c)(c,c)
같은 거 (a,a)(c,c)(c,c)(c,c) : len(conv)=4
중복되는 것 체크 (c,c)(c,c) (c,c)(c,c) : cnt=2
answer = len(s)-len(conv)*step+(len(conv)-cnt)=8-4*1+(4-2)=6
연속이 아닌 것도 카운트 됨
계획 2
conv의 원소를 생성할 때 if문으로 같은 것만 포함하지 말고
전부 담은 후 같은 것은 따로 cnt_coup로 세자
(a,a)(a,c)(c,c)(c,a)(a,c)(c,c)(c,c)
같은 거 cnt_coup=4
중복되는 것 체크 (c,c)(c,c) : cnt=1
answer = len(s)-len(conv)*step+(len(conv)-cnt)=8-4*1+(4-1)=7
def solution(s):
answer = []
for step in range(1, len(s) + 1):
conv = []
cnt_coup = 0
for j in range(int(len(s) / step) - 1):
conv.append((s[j * step:j * step + step], s[j * step + step:j * step + 2 * step]))
if s[j * step:j * step + step] == s[j * step + step:j * step + 2 * step]:
cnt_coup += 1
cnt = 0
for x, y in zip(conv, conv[1:]):
if x == y:
cnt += 1
print(cnt)
answer.append(len(s) - cnt_coup * step + (cnt_coup - cnt))
return min(answer)
쉽지 않네ㅠ
