[백준 2531번] 회전 초밥 - 파이썬

https://www.acmicpc.net/problem/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가지 종류의 초밥을 먹을 수 있다.

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

💡알고리즘 설계

1. 접시를 입력받는다.

2. 접시 리스트에 앞의 k만큼의 접시를 추가한다. (배열 범위 초과 방지)

3. 접시를 하나씩 훑으며 현재 접시에서 시작하여 k개만큼의 접시를 set으로 저장한다.

4. set에 쿠폰 접시를 하나 추가하고, 현재 최대 접시 개수와 현재 set의 길이를 비교하여 더 큰것을 접시 개수로 정한다.

💡코드

import sys
input = sys.stdin.readline

dish=[]
N, d, k, c=map(int, input().split())

for _ in range(N):
    dish.append(int(input()))
dish+=dish[:k]

max_count=0
for i in range(N):
    my_dish=set(dish[i:i+k])
    my_dish.add(c)
    max_count=max(max_count, len(my_dish))

print(max_count)

💡시간복잡도

자동으로 중복 처리를 하기 위해 set을 이용했다.

 

처음에는 초밥 개수인 N개만큼 for문을 돌리고, 그 안에서 먹을 수 있는 접시 개수인 k개 만큼 for문을 이용해 my_dish 리스트에 접시를 추가하려고 했다. 그러나 이중 for문을 하게 되면 N의 최대값인 30000 * k의 최대값인 3000일 경우 9천만으로, 1억에 가깝게 된다. 파이썬에서는 연산 횟수가 2천만일 때 1초가 소요되고, 이 문제의 시간 제한은 1초이므로 이중 for문을 이용하면 시간 초과가 날 것 같았다.

그래서 새 리스트를 만들어 하나씩 추가하는게 아니라, 리스트를 [i:i+k]를 이용해 슬라이싱을 했고, 시간초과가 나지 않았다

 

그러나 시간이 생각보다 오래 걸려 찾아보니... 리스트를 [:]로 슬라이싱하는 방법도 결국 객체를 하나씩 훑는 것이기 때문에 똑같이 시간이 k만큼 걸린다. 결국 for문을 쓰지 않아도 똑같은 것이다...!! (몰랐던 사실..)

 

나는 브루트포스 알고리즘을 이용했지만, 딕셔너리나 슬라이딩 윈도우를 사용하면 더 빠르게 해결할 수 있을 것 같다. 나중에 슬라이딩 윈도우로도 풀어봐야겠다.