[Python] 백준 15961, 2531 회전 초밥

1. 문제 링크

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

15961번: 회전 초밥

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

2531번: 회전 초밥

---

2. 문제 요약

1. k개의 접시 연속으로 먹기 ⇒ 슬라이딩 윈도우
2. 1 조건을 만족한 경우, 쿠폰에 적힌 초밥 먹기 가능

⇒ 먹을 수 있는 초밥 가짓수의 최댓값 구하기 

 

---

3. 아이디어 정리

1. 원형이니 회전초밥 리스트를 2개 이어준다.
2. k개의 접시를 연속으로 먹기 위해 슬라이딩 윈도우를 적용한다.
   • dict를 이용하여 현재까지 먹은 초밥의 종류를 저장한다.

---

4. 문제 풀이

4-1. 내 풀이

 """
손님이 먹을 수 있는 초밥의 가짓수의 최댓값
"""
import sys
from collections import defaultdict

# 접시 수, 초밥 가짓수, 연속해서 먹는 접시 수, 쿠폰 번호
n, d, k, c = map(int, sys.stdin.readline().split())
arr = [int(sys.stdin.readline()) for _ in range(n)]
arr.extend(arr)   # 원형이라서 2개를 이어준다.
left = 0
right = 0
dict_ = defaultdict(int)
result = 0

dict_[c] += 1          # 보너스는 무조건 먹기 

# 1. 처음에 k 구간만큼 먹기
while right < k:
    dict_[arr[right]] += 1
    right += 1

# 2. 슬라이딩 윈도우 적용 
while right < len(arr):
    result = max(result, len(dict_))
    # 1. 맨 왼쪽 초밥 제거
    dict_[arr[left]] -= 1
    if dict_[arr[left]] == 0:  # 삭제된 왼쪽 초밥이 0 이면 dict 삭제 
        del dict_[arr[left]]
    # 2. 오른쪽 초밥 추가하기 
    dict_[arr[right]] += 1
    # 왼쪽 위치 + 1
    left += 1
    # 오른쪽 위치 + 1
    right += 1

print(result)

---

5. 결론

• 슬라이딩 윈도우 문제
• 원형인 경우에 2개의 리스트를 이어줘서 해결 가능