[백준/BOJ] #15961 #2535 회전초밥 [투포인터/슬라이딩윈도우/파이썬/Python]

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

15961번: 회전 초밥

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

2531번: 회전 초밥

 

 

요즘에 투포인터를 이용해서 푸는 문제들이 기출에도 그렇고 요새 종종 나오는 것 같다. 

원형 큐를 만들어서 왼쪽 오른쪽 양방향으로 훑어보는 문제다. 코테 기출에 종종 이런 문제들이 좀 나오는 추세 같다.

이걸 슬라이딩윈도우 알고리즘이라 하나보다. 

 

같은 문제로 실버랑 골드인데

n값이 달라진다. roll.extend(roll)로 리스트 두개연결해서 원형큐를 구현해주었다. 

 

파이썬 코드

#2531_회전초밥
from collections import defaultdict 
n,d,k,c = map(int,input().split())
roll=[]
for _ in range(n):
    roll.append(int(input()))

roll.extend(roll)
d = defaultdict(int)
right,left=0,0

while right < k:
     d[roll[right]]+=1
     right+=1
d[c]+=1 #쿠폰초밥 추가 
answer=0
while right < len(roll):
    answer = max(answer, len(d))
    #왼쪽 초밥 제거 
    d[roll[left]]-=1
    if d[roll[left]]==0:
        del d[roll[left]]
    #오른쪽 초밥 추가하면서 탐색 
    d[roll[right]]+=1
    left+=1
    right+=1


print(answer)

센스껏 파이써닉하게 코드를 짜는 게 연습이 많이 필요한 것 같다.

딕셔너리 말고 앞으로 defaultdict를 애용해야겠다. 물건이다 이 아이.