🔑 오늘의 학습 키워드 : 슬라이딩 윈도우
def solution(s):
def compress(s, length):
compressed = []
prev = s[:length]
count = 1
for i in range(length, len(s), length):
current = s[i:i+length]
if current == prev:
count += 1
else:
if count > 1:
compressed.append(str(count))
compressed.append(prev)
prev = current
count = 1
if count > 1:
compressed.append(str(count))
compressed.append(prev)
return ''.join(compressed)
answer = len(s)
for length in range(1, len(s) // 2 + 1):
compressed_string = compress(s, length)
answer = min(answer, len(compressed_string))
return answer
🗒️ 공부한 내용 본인의 언어로 정리하기
🤔 문제를 보고 든 생각
처음 문제를 보고 brute force + sliding window라고 생각을 했다
그 이유는 s의 제한 조건이 10^3었기 때문에
예상 시간 복잡도가 O(N^2)로 통과할 수 있기 때문이다.
🔑 알고리즘 개요
윈도우의 크기를 생각해보면 1부터 전체 길이의 절반이었다
그리고 이전 윈도우와 다음 윈도우가 같다면 몇 번 압축했는지 (count) 표시해주는 변수를 추가해준다.
for문이 종료된 후 마지막에 조건을 만족했다면 그 부분 또한 포함해줘야 한다.
😱 실수한 부분
입출력 예 #5
문자열은 제일 앞부터 정해진 길이만큼 잘라야 합니다.
따라서 주어진 문자열을 x / ababcdcd / ababcdcd 로 자르는 것은 불가능 합니다.
이 경우 어떻게 문자열을 잘라도 압축되지 않으므로 가장 짧은 길이는 17이 됩니다.
처음에 모든 s의 인덱스에 대해 윈도우를 적용시켰는데
5번 입출력을 보고 그렇게 하는 것이 아니라
처음부터 쭉 윈도우 크기만큼 증가시키는 것이었다.
# 잘못된 부분
# 1씩 증가해서 모든 부분 탐색
for length in range (1,len(s)//2 + 1)
# 옳은 부분
# length만큼 증가하여 윈도우 크기만큼 탐색
for i in range(length, len(s), length)
✅ 오늘의 회고
- 알고리즘에 자주 쓰이는 기법들을 잘 활용해야 한다.
- 최근에 알게된 기법들이 여러가지 있는데 알고리즘은 끝이 없는 것 같다..
#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL
'Coding test' 카테고리의 다른 글
99클럽 코테 스터디 6일차 TIL, 프로그래머스 / 테이블 해시 함수 (0) | 2024.07.27 |
---|---|
99클럽 코테 스터디 5일차 TIL, 프로그래머스 / 베스트앨범 (0) | 2024.07.26 |
99클럽 코테 스터디 3일차 TIL, 프로그래머스/숫자 문자열과 영단어 (2) | 2024.07.24 |
99클럽 코테 스터디 2일차 TIL, 프로그래머스/숫자 카드 나누기도움말 (2) | 2024.07.23 |
99클럽 코테 스터디 1일차 TIL, 프로그래머스 / 뒤에 있는 큰수 (3) | 2024.07.22 |