[백준][Python] 20922번 겹치는 건 싫어

20922번: 겹치는 건 싫어

 

 

코드

n, k = map(int,input().split())
n_list = list(map(int,input().split()))
left = 0
right = 0
cnt = [0] * 1000000
ans = 0

while right < n:
	if cnt[n_list[right]] < k:
		cnt[n_list[right]] += 1
		right += 1
	else:
		cnt[n_list[left]] -= 1
		left += 1
	ans = max(ans, right-left)
    
print(ans)

 

설명

투 포인터 알고리즘이다.

처음에 포인터 left, right가 첫번째 원소를 가리킨다. 만약 right가 가리키는 원소가 k번보다 많이 나오지 않았으면 해당 숫자의 cnt를 증가시키고 right를 한칸 이동시킨다. 만약 k번보다 많이 나오게 되면 left가 가리키는 원소의 cnt 개수를 하나 감소시키고 left를 한칸 이동시킨다.

( right - left )로 현재 수열의 길이를 구할 수 있고, max를 이용해서 최장 길이를 계속 갱신한다.