[ 15961 ] [ Two-Pointer ] 회전 초밥

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

15961번: 회전 초밥

풀이 과정

---

1. 일단 가장 왼쪽 초밥에서부터 연속해서 k개를 선택한다.

   • 이 때, 중복이 있을수 있으므로 초밥의 종류는 set에 저장하고 초밥의 개수는 딕셔너리에 저장한다.

2. 이제 왼쪽에서 한칸, 오른쪽으로 한칸 이동할 것이다.

   • 이전까지의 초밥의 종류가 0부터 k-1이라 하면 다음 초밥의 종류는 1부터 k, ...
   • left와 right를 1씩 증가하면서 배열의 크기를 넘어서는 경우가 있음
     • left = (left + 1) % 배열크기, right = (right+1) % 배열크기
   • 갱신하면서 왼쪽 딕셔너리의 값은 이동 전 1 감소시키고, 오른쪽 딕셔너리의 값은 이동 후 1 증가시킨다.
   • 딕셔너리의 값이 0이 되었다면 set에서 제거하고, 1이 되었다면 set에 추가한다.
   • 초밥의 최대 가짓수를 갱신해 주는데, 이 때 쿠폰 번호가 현재 초밥 종류에 속해 있다면 쓸수 없으므로 그대로, 속해있지 않다면 쓸수 있는 것이므로 1 더한 값으로 비교해 준다.

3. 왼쪽이 배열의 맨 마지막에 도달할때 까지 진행해 준다.

4. 초밥의 최대 가짓수를 출력해 준다.

---

소스 코드

import sys
from collections import defaultdict

input = lambda :sys.stdin.readline().rstrip()

N, d, k, c = map(int, input().split())
sushi = [int(input()) for _ in range(N)]
case = set()
case_count = defaultdict(int)
answer = 0

left = 0
right = k-1

for i in range(k):
    case.add(sushi[i])
    case_count[sushi[i]] += 1

total_case = len(case)+1 if c not in case else len(case)
answer = max(answer, total_case)


for i in range(N):
    case_count[sushi[left]] -= 1
    if case_count[sushi[left]] == 0: case.remove(sushi[left])
    left = (left + 1) % N

    right = (right + 1) % N
    if sushi[right] not in case: case.add(sushi[right])
    case_count[sushi[right]] += 1

    total_case = len(case)+1 if c not in case else len(case)
    answer = max(answer, total_case)

print(answer)