회전 초밥

문제분석

초밥을 연속해서 k개를 먹을 때, 먹을 수 있는 초밥의 최대 가짓수를 구하는 문제이다.

초밥이 회전 벨트 위에서 순환하기 때문에, 먼저 초밥의 종류를 받은 리스트에서 앞의 k-1개 만큼 리스트 뒤에 추가해 주었다. 그리고 이 문제에서는 쿠폰의 번호가 주어지는데 쿠폰 번호에 해당하는 초밥을 추가로 먹을 수 있다. 따라서, 연속으로 초밥을 먹을 때, 쿠폰의 번호와 겹치지 않는 초밥들로 먹을 때 초밥의 가짓수를 최대로 하며 먹을 수 있다.

아래의 그림을 살펴보자.

Crepe

슬라이딩 윈도우 알고리즘이라고도 하는데, 왼쪽부터 순서대로 k개의 원소들을 차례차례 확인해주는 방법이다. 정말 간단함으로 구현방법은 생략하겠다.

여기에 추가로 check 리스트를 만들어 해당 초밥을 몇개 먹는지도 체크해 주었다. 예를 들어서 ‘7 9 7 30’이면, 7번 초밥을 두번 먹음으로, (쿠폰은 신경쓰지 않고)총 3가지의 초밥을 먹을 수 있다. 이렇게 먹는 초밥의 가지수를 왼쪽부터 차례차례 체크해 나가며 최대 가짓수를 찾아보자.

CODE

import sys
read=sys.stdin.readline

n,d,k,c=map(int,read().split())
num=list(int(read()) for _ in range(n))

num=num+num[:k]#회전하는 초밥임으로 앞 k-1개의 초밥을 뒤에 덧붙여준다.
check=list(0 for _ in range(d+1))
check[c]=1 #쿠폰에 적힌 초밥은 기본적으로 한개 포함임으로
l,r=0,k-1
count=0#초밥의 가지수 저장

for i in num[l:r+1]:
    check[i]+=1
    if check[i]==1: count+=1

answer=count
while True:
    check[num[l]]-=1
    if check[num[l]]==0:
        count-=1
    l+=1
    r+=1
    if r == n+k-1: break
    check[num[r]]+=1
    if check[num[r]]==1:
        count+=1
    answer=max(answer,count)

print(answer+1)


틀린 부분이 있을 수 있습니다. 피드백 주시면 고치도록 하겠습니다! 감사합니다.👍

[꼭 다시 풀어보기]