ㅋㅋㅋㅋㅋ 그냥 못풀었음; 피곤한 것도 있지만 이걸 어떻게 차례대로 검사할까 생각이 안 나는...
결국 15분만에 GG치고 정답 봤음. 나중에 다시 풀어봐야지
1. 내 풀이
def solution(s):
answer = 0
for i in len(s):
for k in len(s):
s[k]
return answer
이정도면 그냥 손도 못 댔다고 하는게 좋겠군
1-1. 풀이 도중 생각
1) 최소 2중 for문을 돌려서 1배수라면 1, 2, 3, 4... 2배수라면 2, 4, 6... 구간을 검사하는 알고리즘이 필요할 것 같다
2) 압축 결과 중 가장 짧은 것을 골라야 하니 이전 결과와 지금 결과를 비교하거나, 전체 결과들을 저장해서 가장 짧은 것을 출력\
3) 입력으로 주어지는 문자열이 짧으니 조금 비효율적인 방법을 써도 되지 않을까?
2. 정답
def solution(s):
answer = len(s)
# 1개 단위(step)부터 압축 단위를 늘려가며 확인
for step in range(1, len(s) // 2 + 1): # 어짜피 압축할 수 있는 최대의 step은 len(s) // 2
compressed = ""
prev = s[0:step] # 앞에서부터 step만큼의 문자열 추출
count = 1
# 단위(step) 크기만큼 증가시키며 이전 문자열과 비교
for j in range(step, len(s), step):
# 이전 상태와 동일하다면 압축 횟수(count) 증가
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
3. 새로 공부하게 된 것 or 새삼 다시 알게 된 것
1) 리스트 슬라이싱의 생사여부. 리스트 슬라이싱 안 쓴지 좀 되니까 있는지 까먹었음
'CS > 알고리즘' 카테고리의 다른 글
[이코테] DFS & BFS - 미로 탈출 (0) | 2023.02.03 |
---|---|
[이코테] DFS, BFS - 음료수 얼려먹기 (0) | 2023.02.02 |
[이코테] 구현 - 문자열 재정렬 (0) | 2023.01.28 |
[이코테] 구현 - 럭키 스트레이트 (0) | 2023.01.27 |
[이코테] 구현 - 왕실의 나이트 (0) | 2023.01.26 |