[BOJ/Python] 백준 2531번 - 회전 초밥

백준 #2531 회전 초밥

2531번: 회전 초밥

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

n, d, k, c = map(int, input().split())   # n: 접시 수, d: 초밥 가짓수, k: 연속해서 먹는 접시 수, c: 쿠폰 번호
sushi = [int(input()) for _ in range(n)]   # 초밥 종류
max_kinds = 0   # 초밥 최대 가짓수
que = deque(sushi[:k])

for i in range(n):
    if i != 0:  
        if i <= n/2:
            que.append(sushi[i+k-1])
        else:   # 개수가 반을 넘어가면
            que.append(sushi[k-(n-i)-1])
    kinds = set(que)
    kinds.add(c)
    max_kinds = max(max_kinds, len(kinds))
    que.popleft()

print(max_kinds)

1. 중복된 요소 저장을 허용하지 않는 집합의 특성을 이용한다!
2. 초밥 리스트에서 차례대로 k개의 초밥을 뽑는다.
3. 집합을 통해 중복된 초밥은 제거한다.
4. 쿠폰으로 받은 초밥도 집합에 추가한다.
5. 집합의 크기는 곧 서로 다른 초밥의 최대 가짓수가 된다.

☝🏻 처음에 슬라이싱 기법으로 k개의 초밥을 뽑았는데 시간 초과가 나서 데큐로 바꿨더니 시간 안에 풀렸다!