2531번: 회전 초밥

Memo

어려웠던 부분 😭

• right를 증가시키는 시점과 left를 증가시키는 지점을 정하기가 어려웠습니다.
• 회전 테이블이라는 것을 간과했습니다. 테이블 길이를 2배로 늘려서 해결했습니다.

Code

제출 날짜

2021/04/22

import sys

N, d, k, c = map(int, sys.stdin.readline().split())
belt = []
sushi = dict()
for _ in range(N):
    a = int(sys.stdin.readline())
    belt.append(a)
for i in range(N):
    belt.append(belt[i])
left = 0
right = k - 2
for i in range(right + 1):
    if (belt[i] in sushi):
        sushi[belt[i]] += 1
    else:
        sushi[belt[i]] = 1
ans = 0
while (right < 2 * N - 1):
    right += 1
    if (belt[right] in sushi):
        sushi[belt[right]] += 1
    else:
        sushi[belt[right]] = 1
    if (len(sushi) >= ans):
        if (c in sushi):
            ans = len(sushi)
        else:
            ans = len(sushi) + 1
    sushi[belt[left]] -= 1
    if (not sushi[belt[left]]):
        del sushi[belt[left]]
    left += 1

print(ans)