[백준] 20922 겹치는 건 싫어 / 구현 / Python 실1

https://www.acmicpc.net/problem/20922

 

보자마자 필이 짜르르 옴

이건 슬라이딩 윈도우다

 

윈도우 범위 조절을 위해 start, end 두개 사용

범위 내 숫자 빈도는 딕셔너리 사용

 

현재 윈도우 범위에서 특정 숫자가 K개를 초과하면

start를 움직여서 k개가 되도록 while문을 돌면서 이동

 

윈도우 최장 길이는

end-start+1로 업데이트

 

from collections import defaultdict
n,k = map(int,input().split())

a = list(map(int,input().split()))

count = defaultdict(int)
start=0
max_l = 0

for end in range(n):
    count[a[end]]+=1
    while count[a[end]]>k:
        count[a[start]]-=1
        if count[a[start]]==0:
            del count[a[start]]
        start+=1
    max_l = max(max_l, end-start+1)

print(max_l)