99클럽 코테 스터디 4일차 TIL, 프로그래머스 / 문자열 압축

🔑 오늘의 학습 키워드 : 슬라이딩 윈도우

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