20922번 겹치는 건 싫어

문제

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

접근 방식

투포인터로 l, r을 늘려가며 딕셔너리로 값을 tracking 하는 방식이다.

l = 왼쪽 포인터
r = 오른쪽 포인터

처음에는 l을 늘릴 때마다 전체 딕셔너리 validation 검사를 했는데(=k개를 초과하는지) 시간초과 걸렸다.
ㄴ 당연함. 이렇게 할거면 투포인터를 쓰는 의미가 없음 🫥

r을 늘렸을 때 처음으로 조건에 위배될 수 있으니까 그때 검사하는 건 맞는데 이걸 어떻게 뺄까 고민하다가 요 코드 보고 아이디어 얻음

r을 최대한 늘릴 수 있을만큼 늘리다가 위배될 때 l을 늘려가며 딕셔너리에서 값을 빼면 된다. 그다지 복잡한 아이디어는 아닌데 너무 그 전형적인 투포인터 형식에 얽매여 있다가 오히려 이렇게 생각지 못했다. 많이 풀면서 스스로 틀을 깨는 것도 중요한 듯 ,,

코드

from collections import defaultdict
import sys

input = sys.stdin.readline

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


l, r = 0, 0
cur = defaultdict(int)
cur[arr[0]] += 1
max_len = 1
while l <= r < n:
    r += 1
    max_len = max(r - l, max_len)
    if r == n:
        break
    cur[arr[r]] += 1
    while cur[arr[r]] > k:
        cur[arr[l]] -= 1
        l += 1


print(max_len)