[백준/투 포인터] - 회전 초밥

문제 링크

✅ PyPy3로 제출해야 함

코드

# PyPy3 - 투 포인터
from collections import defaultdict

n, d, k, c = map(int, input().split())
_list = [int(input()) for _ in range(n)]
_list += _list # 원형으로 생각하기 위해 뒤에 똑같은 리스트를 붙여줌
dic = defaultdict(int) # 손님이 먹은 초밥 가짓수

dic[c] += 1 # 쿠폰 초밥 먹기

l, r = 0, 0
_max = 0 # 손님이 먹은 초밥 가짓수 최댓값

# 처음에 초밥 k개 먹기
for _ in range(k):
    dic[_list[r]] += 1
    r += 1

while r < len(_list):
    _max = max(_max, len(dic)) # 초밥 가짓수 갱신
    dic[_list[r]] += 1 
    dic[_list[l]] -= 1
    if dic[_list[l]] == 0: # 초밥을 다 먹었으면
        del dic[_list[l]] # 삭제
        
    l += 1
    r += 1

print(_max)

풀이

문제의 목표

• 손님이 먹을 수 있는 초밥 가짓수의 최댓값 구하기

초밥은 원형으로 이어져있으므로, 먼저 초밥 리스트를 2개 합쳐서 원형으로 만들어준다.

먹을 수 있는 초밥 가짓수의 최댓값은 쿠폰을 무조건 사용하면 구할 수 있다.또한, 쿠폰을 사용하려면 k개의 연속된 초밥을 먹어야 한다.

초밥의 가짓수는 딕셔너리를 이용해서 저장한다.(초밥 번호: 개수)

먼저 쿠폰으로 먹은 초밥을 딕셔너리에 추가한다.(쿠폰은 무조건 쓸거니까 미리 초기화)

그 후 일반적인 투 포인터와 마찬가지로, l=0, r=0로 초기화하고, 초밥 k개를 먹을 때 까지 r을 늘려준다.
그리고 l과 r을 늘리면서 초밥의 가짓수를 갱신한다.(l과 r의 차이는 k로 고정되어있다. 따라서, l은 r의 크기를 넘을 수 없으므로 while문의 조건은 r이 리스트의 범위만 넘지 않은 경우만 확인하면 된다.)