[백준] 20922번 겹치는 건 싫어 파이썬

문제

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

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

입력

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

둘째 줄에는 a1,a2,...an${a_1, a_2, ... a_n}$이 주어진다 (1≤ai≤100000$1 \le a_i \le 100,000$)

출력

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

예제 입력 1

9 2
3 2 5 5 6 4 4 5 7

예제 출력 1

7

예제 입력 2

10 1
1 2 3 4 5 6 6 7 8 9

예제 출력 2

6

제출 답안

• rt를 비교하면서 lt, rt를 증가시키면 된다.

'''
1. 아이디어
- 우선 1씩 증가시킨다.
- counter를 사용하여 k개 이하인지 확인한다. (최댓값이)
2. 시간 복잡도
- 
3. 변수
- max_num int
- counter dict
'''

import sys
from collections import defaultdict
input = sys.stdin.readline

n, k = map(int, input().split())

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

lt, rt = 0, 0
counter = defaultdict(int)
result = 0


while rt < n:
    if counter[num[rt]] < k:
        counter[num[rt]] += 1
        rt += 1
    else:
        counter[num[lt]] -= 1
        lt +=1
    result = max(result, rt - lt)
print(result)