[Gold IV] 회전 초밥 - 15961

문제 링크

성능 요약

메모리: 207616 KB, 시간: 1404 ms

분류

슬라이딩 윈도우, 두 포인터

문제 설명

회전 초밥 음식점에는 회전하는 벨트 위에 여러 가지 종류의 초밥이 접시에 담겨 놓여 있고, 손님은 이 중에서 자기가 좋아하는 초밥을 골라서 먹는다. 초밥의 종류를 번호로 표현할 때, 다음 그림은 회전 초밥 음식점의 벨트 상태의 예를 보여주고 있다. 벨트 위에는 같은 종류의 초밥이 둘 이상 있을 수 있다.

새로 문을 연 회전 초밥 음식점이 불경기로 영업이 어려워서, 다음과 같이 두 가지 행사를 통해서 매상을 올리고자 한다.

1. 원래 회전 초밥은 손님이 마음대로 초밥을 고르고, 먹은 초밥만큼 식대를 계산하지만, 벨트의 임의의 한 위치부터 k개의 접시를 연속해서 먹을 경우 할인된 정액 가격으로 제공한다.
2. 각 고객에게 초밥의 종류 하나가 쓰인 쿠폰을 발행하고, 1번 행사에 참가할 경우 이 쿠폰에 적혀진 종류의 초밥 하나를 추가로 무료로 제공한다. 만약 이 번호에 적혀진 초밥이 현재 벨트 위에 없을 경우, 요리사가 새로 만들어 손님에게 제공한다.

위 할인 행사에 참여하여 가능한 한 다양한 종류의 초밥을 먹으려고 한다. 위 그림의 예를 가지고 생각해보자. k=4이고, 30번 초밥을 쿠폰으로 받았다고 가정하자. 쿠폰을 고려하지 않으면 4가지 다른 초밥을 먹을 수 있는 경우는 (9, 7, 30, 2), (30, 2, 7, 9), (2, 7, 9, 25) 세 가지 경우가 있는데, 30번 초밥을 추가로 쿠폰으로 먹을 수 있으므로 (2, 7, 9, 25)를 고르면 5가지 종류의 초밥을 먹을 수 있다.

회전 초밥 음식점의 벨트 상태, 메뉴에 있는 초밥의 가짓수, 연속해서 먹는 접시의 개수, 쿠폰 번호가 주어졌을 때, 손님이 먹을 수 있는 초밥 가짓수의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2 ≤ k ≤ 3,000 (k ≤ N), 1 ≤ c ≤ d이다. 두 번째 줄부터 N개의 줄에는 벨트의 한 위치부터 시작하여 회전 방향을 따라갈 때 초밥의 종류를 나타내는 1 이상 d 이하의 정수가 각 줄마다 하나씩 주어진다.

출력

주어진 회전 초밥 벨트에서 먹을 수 있는 초밥의 가짓수의 최댓값을 하나의 정수로 출력한다.

풀이

아이디어

우선 코드부터 첨부한다.

import sys
input = sys.stdin.readline

plate, kinda, series, cupon = map(int, input().split())
lane = list(int(input()) for _ in range(plate))*2
# res = [[0, 0] for _ in range(plate+1)]  # 가짓수, 종류수
res = [0]*(plate+1)

sp, ep = 0, series

while sp <= plate:
    window, kind = lane[sp:ep], len(set(lane[sp:ep]))
    # print(window, kind)
    # res[sp][0], res[sp][1] = kind, kind
    res[sp] = kind
    if cupon not in window:
        # res[sp][0] += 1
        res[sp] += 1
        
    sp, ep = sp+1, ep+1

# print(sorted(res, key = lambda x:(-x[0], -x[1])))
print(max(res))

아이디어는 연속으로 먹은 초밥을 슬라이싱하고, 최대한 많은 종류의 초밥을 먹어야하므로, set을 이용해서 중복을 제거한 개수를 저장해주었다.

지금 와서 보니까 문제를 잘못읽은 부분이 있는데, 만약 쿠폰으로 받은 초밥번호가 내가 연속으로 먹는 초밥 시리즈에 없다면 1개를 더해준다. 이부분은 문제에서 "초밥이 없다면 만들어준다"라는 조건을 빼고 봐서 그렇다.

이 코드는 우선 시간초과가 발생한다. 그도그럴것이 6백만 크기의 리스트 인덱싱을 반복하니까 $N \times (N-1)$정도의 연산이 반복된다. 또한 인덱싱은 인덱싱 크기만큼의 연산이 추가로 필요하므로 series를 s라고 했을때 저기에 s를 또 곱해줘야한다..

코드

import sys
input = sys.stdin.readline
from collections import defaultdict

N, d, k, c = map(int,input().split())
sushi = []
for _ in range(N):
    sushi.append(int(input()))
sushi.extend(sushi)

left = 0
right = 0
max_cnt = 0
eat = defaultdict(int)

eat[c] += 1

for right in range(len(sushi)):
    eat[sushi[right]] += 1

    if right >= k-1:
        max_cnt = max(max_cnt,len(eat))
        eat[sushi[left]] -= 1
        if eat[sushi[left]] == 0:
            del eat[sushi[left]]
        left += 1
        
print(max_cnt)

1. 나는 리스트 크기를 2배로 늘릴때 곱 연산을 이용했지만 코드에서는 .extend()를 사용했다.
2. eat이라는 변수에 값이 없는 딕셔너리 (default dict)을 생성하였고, 실제로 시뮬레이션 하듯이 먹고 빼고를 반복한다.
3. 쿠폰으로 주는 초밥은 무조건 먹으므로 c에 1을 더해준다.
4. 슬라이딩 윈도우를 적용해주는데, k 만큼은 무조건 먹고, 만약 오른쪽 포인터가 그 이상이 갔을때, 왼쪽 포인터를 옮겨주고, 해당 위치에 있는 초밥의 개수를 줄여준다
5. 만약 초밥을 줄였을때 개수가 0이라면 해당 키를 삭제시켜 개수를 업데이트해준다.

즉 딕셔너리가 저장하는 값은 각각의 번호의 초밥을 몇개 먹었는가? 를 저장하며, 그 종류의 개수를 세어 가장 큰 값을 정답으로 한다.

---

회고

슬라이딩 윈도우라는 주제를 제대로 풀어본적이 없어 아이디어를 떠올리기 쉽지 않았던 문제.