[백준 2531번] 회전 초밥

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

import sys
from collections import deque

# 회전하는 벨트 위에 여러 가지 종류의 초밥이 접시에 담겨 놓여 있고, 손님은 이 중에서 자기가 좋아하는 초밥을 골라서 먹는다

# 1. 벨트의 임의의 한 위치부터 k개의 접시를 연속해서 먹을 경우 할인된 정액 가격으로 제공
# 2. 각 고객에게 초밥의 종류 하나가 쓰인 쿠폰을 발행하고, 1번 행사에 참가할 경우 이 쿠폰에 적혀진 종류의 초밥 하나를 추가로 무료로 제공
# (만약 이 번호에 적혀진 초밥이 현재 벨트 위에 없을 경우, 요리사가 새로 만들어 손님에게 제공)

input = sys.stdin.readline

n, d, k, c = map(int,input().split())

dictionary = [0]*(d+1)

sushi_list = []

for _ in range(n):
    menu = int(input())
    sushi_list.append(menu)

for i in range(k):
    dictionary[sushi_list[i]] += 1

sushi_list *= 2

value = deque(sushi_list[:k])
value_set = set(value)
value_count = len(value_set)

answer = 0


for i in range(k,n+k):

    dictionary[sushi_list[i-k]] -= 1

    temp = value_count

    if dictionary[sushi_list[i-k]] <= 0:
        temp -= 1
    
    if dictionary[sushi_list[i]] <= 0:
        temp += 1

    dictionary[sushi_list[i]] += 1


    if dictionary[c] <= 0:
        answer = max(answer,temp+1)
    else:
        answer = max(answer,temp)

    value_count = temp


print(answer)

 

이번 문제는 d 종류의 초밥이 N개의 회전 초밥 벨트에 올려져있을 때, 연속 K개의 초밥을 선택하여 만들 수 있는 최대 종류 개수를 구하는 문제이다.

 

먼저 완전탐색으로 K개의 초밥을 하나씩 전부 세게 되면 시간복잡도 O(N*K)가 되어 시간초과가 발생하게 된다.

 

따라서 슬라이딩 윈도우로 풀어야 하는데, 이번 문제는 값들의 합이 아니라 종류를 구하는 문제이므로 dictionary라는 사전 역할을 하는 리스트에 값을 지우고 추가하며 선택한 초밥의 종류를 업데이트해주었다.

 

또한, c번 종류의 초밥의 유무에 따라 최댓값이 달라지므로 업데이트하기 전에 해당 초밥을 이미 선택했는지 확인하고 업데이트해주었다.