[백준 2531] 회전 초밥

문제

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

 

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

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 ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ k ≤ 3,000 (k ≤ N), 1 ≤ c ≤ d이다. 두 번째 줄부터 N개의 줄에는 벨트의 한 위치부터 시작하여 회전 방향을 따라갈 때 초밥의 종류를 나타내는 1 이상 d 이하의 정수가 각 줄마다 하나씩 주어진다.

출력

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

---

입력

N개의 회전 초밥 접시 중 k개의 접시를 연속으로 먹을 때 가장 많은 종류의 초밥을 먹는 경우를 구하는 문제이다

k개라는 범위가 정해졌기에 연속부분집합을 반복적으로 검사해주는 슬라이딩 윈도우를 사용하면 될 것 같다

 

추가로 신경 쓸 부분은 "쿠폰"이다. 연속으로 먹은 k개의 접시에 c라는 초밥이 없다면 c 초밥을 추가로 제공해준다고 한다

 

먼저 k초밥을 입력받으며 나의 초밥 리스트에 넣어줬다

for _ in range(k):
    i = int(input())
    pick.append(i)
    kdish.append(i)

형성된 pick 리스트는 내가 처음으로 먹은 k개의 연속부분집합이 된다

 

res = len(set(pick))
if c not in pick:
    res += 1

set을 사용하여 중복된 종류의 초밥을 제외한 초밥의 개수를 res에 넣어주었다

c초밥이 앞서 담은 pick리스트에 존재하지 않는다면 추가로 c초밥을 받을 수 있기에 res += 1을 해주었다

 

for _ in range(k,N):
    pick.popleft()
    pick.append(int(input()))
    tmp = set(pick)
    if len(tmp) >= res:
        res = len(tmp)
        if c not in tmp:
            res += 1

이후에는 deque를 사용하여 리스트의 가장 앞쪽에 위치한 초밥을 빼주고

다음으로 입력받는 초밥을 리스트에 넣어주었다

마찬가지로 set로 중복 초밥을 제거한 초밥의 개수를 res와 비교하여 업데이트 해주었고 쿠폰 c초밥 처리도 해주었다

 

여기까지 코드를 짜고 넣었는데 틀렸다

시간복잡도를 계산해봤을 때 빠듯했기에 시간 초과가 날 수도 있다고 생각했지만 틀리는건 생각하지 못했기에 당황..

 

문제를 다시 천천히 읽어보니 "회전"초밥이다. 마지막으로 입력받은 초밥이 끝이 아닌 처음으로 입력받은 초밥과 이어지는 특성을 고려해야한다

for i in range(k):
    pick.popleft()
    pick.append(kdish[i])
    tmp = set(pick)
    if len(tmp) >= res:
        res = len(tmp)
        if c not in tmp:
            res += 1

따라서 처음에 입력받은 k개의 초밥만큼 더 회전시켜 검사를 진행하였다

 

 

set는 O(n)을 갖기에 빠지는 초밥과 넣는 초밥을 따로 검사해주지 않고 set을 사용하였다

in은 리스트를 검사할 때는 O(n)이 걸리지만 set을 검사할 때는 hash를 통해 저장되므로 평균적으로 상수 시간이 걸린다

만약 쿠폰 c의 검사를 모든 반복문에 수행했다면 시간초과가 났을 것으로 예상된다