[Python] 백준 2531 : 회전 초밥

www.acmicpc.net/problem/2531

2531번: 회전 초밥

풀이 방법

• 문제 이해 : 초밥을 k개 연속으로 먹었을 때 먹을 수 있는 최대 종류를 구하는 것이다.
• left부터 right까지 먹을 때, 먹을 수 있는 초밥의 종류를 canEat이라는 딕셔너리에 저장한다.
• 먹을 수 있는 초밥의 종류의 개수는 cnt에 저장한다. 
• '회전' 초밥이기 때문에 0~k까지 뿐만아니라 n-1~k-1까지 순환할 수 있음을 잊으면 안된다. -> right = (left+k) % N으로 구현

전체 코드

from collections import defaultdict
N, d, k, c = map(int, input().split())
arr = []
for i in range(N):
    arr.append(int(input()))

canEat = defaultdict(int)
cnt = 1
canEat[c] = 1
for i in range(k):
    if canEat[arr[i]] == 0:
        cnt += 1
    canEat[arr[i]] += 1
answer = cnt
for left in range(N):
    right = (left+k)%N
    canEat[arr[left]] -= 1
    if canEat[arr[left]] == 0:
        cnt -= 1
    if canEat[arr[right]] == 0:
        cnt += 1
    canEat[arr[right]] += 1
    answer = max(answer, cnt)
print(answer)