[Python] 백준 / gold / 15961번 (회전초밥)

문제 링크 : https://www.acmicpc.net/problem/15961

슬라이딩 윈도우 문제이다. 처음에 deque를 이용해서 popleft(), append를 진행했지만, 초밥을 몇 가지 먹는지 카운팅 하는데서 len(set(deque)) 코드를 작성해서 그런지 시간복잡도 통과를 하지 못했다.

파이썬의 dictionary 자료형을 사용하고, Pypy로 제출 했더니 통과할 수 있었다

정답 코드

from collections import defaultdict
import sys
N, d, k, c = map(int, sys.stdin.readline().split())

belt = []
for _ in range(N):
    x = int(sys.stdin.readline())
    if x == c : coupon = True
    belt.append(x)

belt += belt[:k-1]
answer = 0
chobab = defaultdict(int)
kind = 0

for i in range(k):
    if chobab[belt[i]] == 0:
        kind += 1
    chobab[belt[i]] += 1


for start in range(k, len(belt)):

    if chobab[belt[start-k]] == 1:
        chobab[belt[start-k]] -= 1
        kind -= 1
    elif chobab[belt[start-k]] > 1:
        chobab[belt[start-k]] -= 1

    if chobab[belt[start]] == 0:
        chobab[belt[start]] += 1
        kind += 1
    else:
        chobab[belt[start]] += 1

    if chobab[c] == 0:
        answer = max(answer, kind + 1)
    else:
        answer = max(answer, kind)

print(answer)