[코딩테스트][백준] 🔥 백준 15961번 "회전 초밥" 문제: Python으로 완벽 해결하기! 🔥

문제 링크

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

🕒 Python 풀이시간: 30분

import sys
from collections import deque

input=sys.stdin.readline

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

dishes=dishes*2
now=deque(dishes[:k])
nowSet=set(now)
typeDict=dict()
for i in dishes[:k]:
    if i in typeDict:
        typeDict[i]+=1
    else:
        typeDict[i]=1

answer=0
end=k-1
start=0
while True:
    num=len(nowSet)
    if c not in nowSet:
        num+=1
    answer=max(answer,num)
    end+=1
    start+=1
    if end>=len(dishes):
        break
    if dishes[end] in nowSet:
        typeDict[dishes[end]]+=1
    else:
        nowSet.add(dishes[end])
        typeDict[dishes[end]]=1
    if typeDict[dishes[start-1]]-1==0:
        nowSet.remove(dishes[start-1])
        del typeDict[dishes[start-1]]
    else:
        typeDict[dishes[start-1]]-=1

print(answer)

회전 초밥집의 비밀: 최대 가짓수 찾기 도전! 🍣🔍

회전 초밥집에서 연속한 K개를 고를 때, 최대의 가짓수를 찾는 방법이다. 대표적인 슬라이딩 윈도우 문제이면서 투포인터 문제이다. 과일 탕후루 문제에서 크게 대였었다...

먼저 N의 크기가 3,000,000이기 때문에 이중 for문으로는 풀 수 없다. 그렇다면 1회성 순환을 할 방법을 찾아야 하는데 이때 사용할 수 잇는 방법이 슬라이딩 윈도우이다. 크기를 고정하면서 앞에꺼를 추가하고 뒤에꺼를 빼는 방식으로 계산해 나가는 방법이다. 이 때, 주의해야할 점은 회전형이기 때문에 똑같은 배열을 이어붙여서 2개로 사용해야 한다는 것이다.

이때, 우리가 구해야 하는 것이 종류이기 때문에 중복 여부를 체크하기 위해 set를 사용하였다. 물론 dict의 keys를 len으로 길이로 찾아도 가능할 거 같다. 앞으로 나아갔을 경우, 이미 우리가 가지고 있는 종류라면 갯수를 늘리고 그렇지 않으면 dict에 추가한다. 뒤에 있는걸 뺄 경우에도 빼었을 때, 종류가 사라진다면 dict에서 지운다. 만약 종류가 사라지지 않으면 단순 감소시킨다. 이렇게 매번 종류의 갯수를 구해주면 된다.

이렇게 Python으로 백준의 "회전 초밥" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊