백준 15961 회전 초밥 Python

🐸 문제 정보

15961번: 회전 초밥

 

🤖 알고리즘

슬라이딩 윈도우

 

⏱️ 풀이 시간

47.30m

 

📝 풀이

슬라이딩 윈도우의 정석 같은 문제였다.

풀이 자체가 복잡하지 않은데도, 처음에 k개까지 초기 설정하는 부분에서 헛디뎌서 검색까지했다.

1. 0부터 k-1번 접시까지 개수를 딕셔너리에 초기화한다.
   • 이 때, 쿠폰 접시의 경우 기본적으로 1개를 추가해준다
2. 이후 반복문을 돌면서 start가 n에 닿기 전까지 k개를 슬라이딩 윈도우하며 비교한다.
   • 이 때, 만약 start 부분의 접시를 뺐는데 0개가 된다면 딕셔너리의 key를 pop해서 개수에 포함되지 않도록 한다.

 

🧑‍💻 나의 답

# pypy3

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

n, d, k, c = list(map(int, input().rstrip().split()))
dishes = [int(input().rstrip()) for _ in range(n)]

start, end = 0, k
res = 0
dtype = defaultdict(int)
for i in range(0, k):
    dtype[dishes[i]] += 1
dtype[c] += 1

while start != n:
    res = max(res, len(dtype))
    dtype[dishes[start]] -= 1
    dtype[dishes[end % n]] += 1
    if dtype[dishes[start]] == 0:
        dtype.pop(dishes[start])
    start += 1
    end += 1

print(res)