[BOJ/Python] 15961_회전 초밥

문제 출처:https://www.acmicpc.net/problem/15961

15961번: 회전 초밥

 

문제

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

 

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

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 이하의 정수가 각 줄마다 하나씩 주어진다. 

출력

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

예제 입력 1

8 30 4 30
7
9
7
30
2
7
9
25

예제 출력 1

5

 

예제 입력 2 

8 50 4 7
2
7
9
25
7
9
7
30

예제 출력 2 

4

 

---

풀이

 

할인 행사에 참여하여 가능한 많은 종류의 초밥을 먹을 수 있는 경우를 찾아야 한다.

연속된 k개의 초밥의 종류를 확인하는 경우이므로 투 포인터를 이용하였다.

우선 초밥의 종류를 확인해야 하므로, 같은 종류의 초밥을 선택하였을 경우는 한 가지 종류로 취급해야 한다.

따라서 처음 문제에 접근하였을 때 python의 set 자료형을 이용하여 문제를 해결하려 하였다.

• set 자료형을 이용할 경우, 중복이 허용되지 않기 때문에 set 자료형의 원소의 개수가 곧 초밥 종류의 개수이다.
• 원소를 추가할 때, 내부에 존재하는 지 확인할 필요가 없기 때문에 편리하다.
• 하지만, set 자료형의 원소를 뺄 때 문제가 생긴다.

예제 입력 1의 경우를 살펴보면 다음과 같다. 우선 쿠폰에 대한 부분은 빼고, 연속된 k개의 초밥을 선택하는 경우만 살펴보자.

우선 k가 4이므로, 연속된 네개의 초밥을 set에 저장하게 되면 7,9,30 총 세 종류의 초밥을 선택함을 알 수 있다. 여기서 한 칸씩 오른쪽으로 이동하여 초밥의 종류가 가장 많은 경우를 찾아야 한다.

 

포인터를 한 칸씩 이동하여 기존의 빨간색 포인터의 원소는 제거하고, 새로운 파란색 포인터의 원소를 추가하였다. 그런데 여기서 문제가 생긴다. 지금 상황에서 초밥의 종류는 2,7,9,30 총 4가지 여야 하지만, 결과는 {2,9,30}으로 나오게 된다.

즉,  set 자료형은 중복이 허용되지 않으므로 초밥의 종류를 구하기는 간편하지만, 원소를 제거할 때 내부에 같은 종류의 원소가 있다면 이와 같은 문제가 생긴다.

그래서 다음과 같은 방법들을 생각해봤다.

 

우선 회전 초밥을 구현하기 위해 주어진 초밥의 리스트를 두 배로 확장시킨다. (맨 끝과 맨 처음이 연결될 수 있도록)

1. 우선 제일 처음 k개의 초밥들을 set에 넣는다. 쿠폰으로 받는 초밥 c는 항상 set에 존재해야 하므로, set에 c를 넣어준다.
2. deque 자료형을 이용한다.
3. popleft를 통해 제일 왼쪽 원소 하나를 뽑아낸다.
4. popleft를 통해 뽑아낸 원소가 c가 아니면서 deque에 존재하는지 확인하고, deque에 없다면 set에서도 제거한다.
5. append를 통해 제일 오른쪽 원소를 추가하고, set에도 add 해준다.
6. set의 원소의 개수를 구하여 최댓값을 구한다.

하지만 이 경우 시간초과가 나왔다.

그래서 딕셔너리 자료형을 이용한 방법을 생각했다.

1. 초밥의 종류를 key로 하고, 그 종류의 개수를 value로 하는 딕셔너리를 만들어 처음 k개의 초밥들을 딕셔너리에 추가한다.
2. 그리고 쿠폰으로 받는 초밥 c의 value도 1 증가시킨다. (들어온 만큼 나가는 것이기 때문에 초밥의 value들은 음수가 될 수 없다. 따라서 c의 value 또한 항상 1 이상이 된다.)
3. 포인터를 한 칸씩 오른쪽으로 이동하면서 왼쪽 포인터가 가리키는 초밥의 value는 1 감소시키고, 오른쪽 포인터가 가리키는 초밥의 value는 1 증가시킨다.
4. 반복문을 이용하여 딕셔너리의 value가 1 이상인 것들의 개수를 구하여 최댓값을 구한다.

이 경우 또한 시간초과가 나왔다. 아무래도 초밥의 종류의 개수를 구하는 과정에서 딕셔너리의 모든 key의 value를 확인해야 하기 때문에 선택하지 않은 초밥들의 value까지도 구하게 되고 그만큼 시간도 오래 걸리게 된다.

그래서 현재 선택하지 않은 초밥들(value가 0인 초밥)은 딕셔너리에서 삭제하는 방법을 이용하였다.

코드는 다음과 같다.

 

import sys
from collections import defaultdict
 
n,d,k,c = map(int,sys.stdin.readline().split())
n_list = []
for _ in range(n):
    n_list.append(int(sys.stdin.readline()))
 
n_list.extend(n_list)
n_dict = defaultdict(int)
 
n_dict[c] = 1
 
for i in range(k):
    n_dict[n_list[i]]+=1
 
 
max_len = len(n_dict)
 
start = 0
end = k-1
 
while end<n+k:
    n_dict[n_list[start]]-=1
    if n_dict[n_list[start]]==0:
        del n_dict[n_list[start]]
    
    start+=1
    end+=1
 
    n_dict[n_list[end]]+=1
    
    max_len = max(max_len,len(n_dict))
 
 
print(max_len)

 

• collections 모듈의 defaultdict 존재하지 않는 key에 대한 연산을 할 때 디폴트 값을 기준으로 key:value를 생성해 준다.
• 여기서 defulatdict(int)를 사용하였고, int의 경우 디폴트 값이 0이다. 이를 이용하여 기존 딕셔너리에 없는 새로운 초밥의 종류를 발견하였을 때, 따로 생성해 주지 않고 +1을 해주게 되면 해당 초밥의 value가 1로 설정된다.
• 여기서 초밥의 value가 0이 된 것을 딕셔너리에서 삭제해 줌으로써 초밥들의 value가 1 이상인 것을 탐색하지 않고, 딕셔너리의 존재하는 key의 개수를 구하는 방식으로 시간을 단축시켰다.