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

문제

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

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

입력

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

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

출력

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

풀이
dp를 사용해서 풀려다가 도저히 안풀려서 찾아보니 투 포인터 문제였다
익숙하지 않은 유형이라 투포인터 생각을 못해봤는데 익숙해지면 좋을 것 같다

left와 right라는 두 개의 포인터를 수열의 맨 처음에 두고 수마다의 등장 횟수를 세는 dict를 선언해준다
right가 가리키는 수가 dict에 없다면 추가해주고 0값을 부여한다
right가 가리키는 수의 등장 횟수가 k가 아니라면 등장횟수를 1 추가하고 right를 오른쪽으로 한 칸 이동시킨다
만약 right가 가리키는 수의 등장 횟수가 k라면 left가 가리키고 있는 숫자의 등장 횟수를 1차감하고 오른쪽으로 한 칸 이동한다
그러면서 현재 right가 가리키고 있는 숫자의 등장 횟수가 다시 k가 아니게 되면 right가 움직이는 것이다
이렇게 함으로써 수열의 중간에 최장 연속 부분 수열이 존재하는 경우까지 찾아낼 수 있다
while 문을 도는 동안 계속해서 max_cnt를 갱신해주는데, max_cnt는 right에서 left를 빼서 구할 수 있다

코드

import sys

n, k = map(int, sys.stdin.readline().split())
a = list(sys.stdin.readline().split())

cnt = dict()

left, right = 0, 0
max_cnt = 0
while right < n:
    if a[right] not in cnt:
        cnt[a[right]] = 0
        
    if cnt[a[right]] != k:
        cnt[a[right]] += 1
        right += 1
        
    else:
        cnt[a[left]] -= 1
        left += 1

    max_cnt = max(max_cnt, right-left)
print(max_cnt)