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

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

---

문제

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

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

입력

첫째 줄에 정수 𝑁 (1≤𝑁≤200000)과 𝐾$K$ (1≤𝐾≤100)가 주어진다.

둘째 줄에는 𝑎1,𝑎2,...𝑎𝑛이 주어진다 (1≤𝑎𝑖≤100000)

출력

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

---

투 포인터를 활용하여 해결하였다.

import sys
input = sys.stdin.readline

from collections import defaultdict

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

cntDict = defaultdict(int)
max_ = -1

st = 0
ed = 0
while ed < N:
    cntDict[arr[ed]] += 1
    
    while cntDict[arr[ed]] > K:
        cntDict[arr[st]] -= 1
        st += 1
    
    ed += 1
    max_ = max(max_, ed - st)

print(max_)