[백준/Python] Silver I #20922 겹치는 건 싫어

20922번: 겹치는 건 싫어

문제

홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 K개 이하로 들어 있는 최장 연속 부분 수열의 길이를 구하려고 한다.

 100,000 이하의 양의 정수로 이루어진 길이가 N인 수열이 주어진다.  이 수열에서 같은 정수를 K개 이하로 포함한 최장 연속 부분 수열의 길이를 구하는 프로그램을 작성해보자.

입력

첫째 줄에 정수 N (1 ≤ N ≤ 200,000)과 K (1 ≤ K ≤ 100) 가 주어진다.

둘째 줄에는 a_1, a_2, ... a_n 이 주어진다 (1 ≤ a_i ≤ 100,000)

출력

조건을 만족하는 최장 연속 부분 수열의 길이를 출력한다.

풀이

import sys
input = sys.stdin.readline

n, m = map(int,input().split())
li = list(map(int,input().split()))

left = 0
right = 0
cnt = [0] * (max(li)+1)
ans = 0

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