[BOJ: 20922] - Python / 파이썬 - 겹치는 건 싫어

문제

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

시간 복잡도

• n만큼 순회(r) + 최대 n만큼 순회(l) -> $O(n)$
• n의 최대값이 200,000이므로 충분하다.

문제 접근법

1. 현재 범위의 수를 카운트 하기 위한 딕셔너리를 정의한다.
2. 시작과 끝 숫자를 나타낼 두 변수를 정의한다.(초기엔 모두 0)
3. 끝 숫자가 n이 될 때 까지 순회한다.
   3-1. 끝 숫자의 개수가 k개 미만인 경우, 끝 숫자의 카운트를 증가시키고 현재 끝 숫자를 1 늘려준 후 시작부터 끝의 범위를 구한다.
   3-2. 끝 숫자의 개수가 k개 이상인 경우, 시작 숫자의 카운트를 감소시키고 현재 시작 숫자를 1 늘려준다.
4. 3-1에서 구했 던 범위 중 가장 큰 범위를 출력한다.

코드

# BOJ
# S1 - 20922(겹치는 건 싫어)

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

n, k = map(int, input().split())
nums = list(map(int, input().split()))
cnt = defaultdict(int)
l, r = 0, 0
ans = 0

while r < n:
    if cnt[nums[r]] < k:
        cnt[nums[r]] += 1
        r += 1
        ans = max(ans, r - l)
    else:
        cnt[nums[l]] -= 1
        l += 1
    
print(ans)