[백준] 15961번 회전 초밥 파이썬 풀이

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

---

1. 풀이

• 입력이 매우 크므로 일반 input() 대신 빠른 sys.stdin.readline()을 사용하자.

N의 크기가 무려 3,000,000이다. 알고리즘이 정답이더라도, 입력 받는 데서 시간이 지체되면 결국 실행 시간이 오래 걸리게 된다. 실제로 오랜만에 백준을 풀어서 습관처럼 input()을 사용했다가 시간 초과가 났었다.

 

 

• 어떤 초밥을 몇 개 먹었는지 저장하는 리스트(dishes)를 사용하자.

리스트의 인덱스가 초밥의 종류를 나타내고, 해당 인덱스의 값이 고객이 그 초밥을 의미한다.

고객이 먹을 수 있는 초밥 가짓수의 최대값은, 고객이 연속해서 먹은 k개의 접시에 쿠폰 번호 c가 포함되어 있지 않은 경우이다. 이를 다르게 생각하면 고객이 일단 무조건 쿠폰 번호에 해당하는 초밥을 먹고 시작한다고 볼 수 있다! 따라서 이 dishes 리스트의 c 인덱스 값을 1로 초기화해두자.

 

 

• 처음에 연속해서 먹은 k개의 접시에 담긴 초밥을 저장해두고, 한 칸씩 옆으로 이동하자.

일명 슬라이딩 윈도우이다. i부터 (i + k - 1)번째 접시까지 먹었을 때의 먹은 각 초밥 개수와 그 가지수를 저장해뒀다가, 한 칸 옆으로 이동하면서 기존 데이터에 변화를 주는 방식이다.

 

 

• 가지수의 변화는 기존에 특정 초밥을 먹은 회수가 0이거나 1일 때이다.

옆으로 이동해서 제외되는 초밥을 1회 먹었었다면 초밥 가지수는 줄어든다. 반면 새로 먹을 초밥을 0회 먹어봤다면, 즉 아직 먹어보지 못했다면 초밥 가지수는 늘어난다.

위 그림을 가지고 예시를 들어보자. 1번째부터 4번째 접시까지 먹으면 (2번 초밥 1회), (7번 초밥 1회), (9번 초밥 1회), (30번 초밥 1회)를 먹으며 초밥 가지수는 4이다.

한 칸 옆으로 이동하면 1번째 초밥인 9번 초밥이 빠진다. 이때 기존 9번 초밥은 1회밖에 먹지 못했기 때문에 9번 초밥이 빠지면 총 먹은 회수가 0이 되어 초밥 가지수는 3이 된다. 반면에 5번째 초밥인 7번 초밥을 먹더라도, 기존에 7번 초밥은 이미 먹은 적이 있기 때문에 가지수에는 변화가 없고 먹은 회수만 2회로 늘어날 뿐이다.

 

 

 

2. 정답 코드

import sys

input = sys.stdin.readline

N, d, k, c = map(int, input().split())
belt = [int(input()) for _ in range(N)]
answer = -1

dishes = [0] * (d + 1)
dishes[c] = 1
count = 1

# 초기 세팅
for i in range(k):
    if dishes[belt[i]] == 0:
        count += 1
    
    dishes[belt[i]] += 1

# sliding window
answer = count
for i in range(N):
    j = (i + k) % N

    if dishes[belt[j]] == 0:
        count += 1
    dishes[belt[j]] += 1

    if dishes[belt[i]] == 1:
        count -= 1
    dishes[belt[i]] -= 1

    answer = max(answer, count)

print(answer)