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

1. 코드

import sys
from collections import defaultdict

max_ans = 0
n, d, k, c = map(int, sys.stdin.readline().split())
susi = [int(sys.stdin.readline().rstrip()) for _ in range(n)]
susi.extend(susi[:k])
d = defaultdict(int)

# init value
for i in range(k):
    d[susi[i]] += 1
ans = len(d.keys())

for start in range(1, len(susi)-k):
    end = start+k

    d[susi[end-1]] += 1
    d[susi[start-1]] -= 1
    if d[susi[start-1]] == 0:
        del d[susi[start-1]]

    if c not in d:
        max_ans = max(max_ans, len(d.keys()) + 1)
    else:
        max_ans = max(max_ans, len(d.keys()))
print(max_ans)

2. 후기

파이썬의 사전 자료형을 사용하여 푸는 문제이다.
이 코드에서 사전형의 인스턴스 객체인 d를 통해 사용한 연산자는 모두 O(1)의 시간 복잡도만 소요된다.