20922 겹치는 건 싫어

1. 문제

문제는 링크에 들어가면 있다.

2. 정답 코드

문제의 내 정답 코드는 다음과 같다.

import sys
read = sys.stdin.readline

N,K = map(int,read().split())
array = list(map(int,input().split()))

# 이거 다 돌수밖에없지만
# 이것도 슬라이딩 윈도우 문제인듯.

save_dict = {}
from collections import deque

save_list = deque()
best_length = 0
for a in array :


    if save_dict.get(a) is None:
        save_list.append(a)
        save_dict[a] = 1
    else :
        # 여기선 K를 넘냐 안넘냐를 확인.
        # print(a,save_dict.get(a),save_list)
        if save_dict.get(a) >= K :
            # 파악한 후, 슬라이딩윈도우 방식으로 처음 요소를 제거하고 마지막 요소를 추가해.
            # 근데 중복되는 요소가 어디에 있는지 알 수 없음 그러니까 여기서 지금 수 a가 줄때까지
            # 숫자를 버려버려야해. 동시에 dict의 수도 줄이기.
            while save_dict.get(a) >= K :
                left_val = save_list.popleft()
                # print(save_list)
                save_dict[left_val] -= 1

            # 끝나면 다시 원래대로 for문으로 돌아간다.
            save_list.append(a)
            save_dict[a] += 1
        else :
            save_list.append(a)
            save_dict[a] += 1

    best_length = max(best_length,len(save_list))

print(best_length)

3. 풀이 및 생각

문제 풀이

이 문제는 슬라이딩 윈도우를 이용하는 문제다. 핵심은 모든 정수들을 훑어보면서 길이가 가장 긴 연속된 부분수열을 찾는 것인데, 이게 정수들의 최대 개수가 20만개여서 이중 반복문이 형성된다면, 무조건 시간초과가 날 수 밖에 없는 문제다. 따라서 하나의 반복문으로 문제를 해결해야하는데, 그러기 위해선 슬라이딩 윈도우를 사용해야했다.

부분수열의 최대 값을 항상 저장토록하고, K개 이하 까지만 겹치는걸 허락하는걸 생각해야한다. 그리고 dictionary를 잘 이용하는 것도 포인트. 왜냐하면 해당 숫자가 몇번 나왔는지 파악하려면 list를 쓰는거보다 dict을 쓰는게 너무나도 효율적이기 때문이다.

K개 초과가 되는 순간 queue형식을 빌어서 popleft를 통해 K개 이하가 될때까지 pop을 해야한다. 그리고 다시 for문을 반복한다. 물론 그때마다 부분수열 길이의 최대값을 저장하는 것도 잊지 말아야한다.

나의 생각

슬라이딩 윈도우란 개념을 배운 후, 또 다른 코딩의 길이 열린 것 같은 느낌이다. 데이터를 훑어보면서 굉장히 효율적으로 진행할 수 있기 때문에 이 개념은 나중에도 매번 잘 쓰일 것 같다.