프로그래머스 카카오 문자열 압축 문제이다.
https://programmers.co.kr/learn/courses/30/lessons/60057
처음에는 문자열의 크기를 반으로 나눈 크기부터 앞에 문자열과 같은지 비교하면서 확인하는 방식으로 구현했었다.
def div_ck(s, scale):
idx = 0
cnt = 1 # 중복되는 단어 개수
result = ""
tmp = ""
while idx < len(s):
frnt = s[idx:scale + idx] # 앞 부분
back = s[scale + idx :] # 뒷 부분
if len(frnt) > len(back):
return cnt
if frnt == back[:len(frnt)]: # 일치하는 경우
cnt += 1
idx += len(frnt) # idx
else: # 일치하지 않는 경우
if cnt > 1:
result += str(cnt) + frnt
cnt = 1
else:
if len(tmp)
tmp += s[idx]
idx += 1
return result
def solution(s):
div_scale = len(s) // 2 # 나누는 단위
# div_ck(s, div_scale, 0)
return div_ck(s, 3)
그런데 이러면 aabaabb의 경우 2aa2bb 이런식으로 될거같은 생각에 뭔가 잘못된 것 같아서 틀렸다고 생각했다. 그런데 문제를 다시 보니까 지금까지 문제를 잘못 이해하고 있었다는 것을 깨달았다. 앞에부터 해당 크기 만큼 잘라서 앞에 문자랑 같은지 확인하는 방식이였다.
다시 말해서 abbcbbc 의 경우 a2bbc 가 되는게 아니라 3 크기로 자르는 경우 abb/cbb/c 로 잘려서 압축이 안되는 것이다. 문제 자체를 잘못이해한것을 깨달고 문제를 다시 풀어봤다.
def div_ck(s, scale):
i = 0
result = 0
cnt = 1
while i < len(s):
frnt = s[i:scale + i] # 앞 부분
back = s[scale + i :] # 뒷 부분
if len(frnt) > len(back):
if cnt == 1: # 같은게 없었는데 끝난경우
result += len(s[i:])
else:
result += len(str(cnt)) + len(frnt) + len(back)
break
if frnt == back[:len(frnt)]: # 일치하는 경우
cnt += 1
i += len(frnt) # i
else:
if cnt > 1:
result += len(str(cnt)) + len(frnt)
i += len(frnt) # 이미 같은 적이 있어서 그 길이만큼은 지나가야함
cnt = 1
else:
if i == 0: # 처음부터 잘려야한다
result += len(frnt)
i += len(frnt)
else:
result += 1
i += 1
return result
def solution(s):
scale = len(s) // 2
result = len(s)
tmp = 0
while scale >= 1:
result = min(result, div_ck(s, scale))
scale -= 1
return result
위와 같이 풀었는데 기본적으로 주어진 테스트케이스는 통과했지만 실제 채점에서는 몇개의 테스트케이스가 틀리게 나왔다. 아마도 모든 경우의 수를 일일히 처리해주는 과정에서 예외 케이스에 대한 처리가 부족해서 틀린 것 같았다. 그래서 이번에는 문자열을 주어진 크기만큼 자른 다음에 확인하는 방식으로 바꾸었다.
def div_ck(s, scale):
i = 0
div_arr = []
result = 0
while i < len(s):
div_arr.append(s[i:i+scale])
i += scale
tmp = None
cnt = 1
for i in div_arr:
if tmp is None: # 반복문이 처음 일 때
tmp = i
result += len(tmp)
continue
if i == tmp: # 이전 단어와 같을 떄
cnt += 1
else:
if cnt != 1:
result += len(str(cnt))
cnt = 1
tmp = i
result += len(i)
if cnt > 1:
result += len(str(cnt))
return result
def solution(s):
scale = len(s) // 2
result = len(s)
while scale >= 1:
result = min(result, div_ck(s, scale))
scale -= 1
return result
정답은 구했지만 너무 많은 시간을 소비했다. 아에 처음부터 접근을 잘했거나 아니면 문제를 꼼꼼히 읽었거나 했으면 더 짧은 시간만에 풀 수 있었을 것 같았다.
문제를 한 4일 정도 풀어봤던 것 같다. 물론 짬짬히 공부할 것 하고 남은 시간에 풀어봐서 4일이나 걸렸다. 접근을 하지도 못한 경우에는 해설을 바로 보았을 것 같은데 뭔가 시간을 할애하면 풀 수 있을 것 같아서 계속 풀어봤던 것 같다. 해설지를 보니까 핵심 개념은 비슷했는데 앞에 문자와 확인하는 방식을 그냥 반복문을 사용했는데 for i in range(stmp, len(s), step)
이런식으로 step
크기만큼 반복문을 진행 할 수 있다는 점을 나는 놓친것 같다. 그래서 코드를 더 복잡하게 짠 것 같다.
역시 알고 있는 것과 활용하는 것에 대한 차이는 분명히 있는 것 같다