백준 2531번: 회전 초밥 (S1) - Python 풀이

문제 설명

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가지 종류의 초밥을 먹을 수 있다.

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

입력

첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,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개씩 먹을 때 먹을 수 있는 가장 많은 종류의 회전초밥의 개수를 출력합니다. 단, 특정 초밥은 쿠폰 쓰면 k개에 추가로 1개 더 먹을 수 있습니다.

배고프네요.

풀이 과정

처음에 N번 도는 for문, k번 도는 for문 써서 2중 for문으로 풀었는데 시간 초과가 났습니다.

배열 슬라이싱으로는 ‘회전’ 초밥을 못 구현하고… 이동할 때마다 범위 k만큼 잡아야 하는데, 어떻게 2중 for문을 없앨 수 있지? 싶어서 질문 게시판을 보고 ‘슬라이딩 윈도우’ 방법을 알아왔습니다.

크기가 k로 고정된 윈도우를 한 칸씩 이동시키는데, 오른쪽으로 한 칸씩 이동하게 되니까 맨 왼쪽 값은 제거되고, 맨 오른쪽 값이 새로 추가됩니다.

이때, 왼쪽 값을 제거하기 위해 deque를 사용합니다. deque에는 popleft라는 효자 함수가 있기 때문입니다.

정답 코드

from collections import deque

# 회전 초밥 벨트에 놓인 접시의 수 N,
# 초밥의 가짓수 d, 
# 연속해서 먹는 접시의 수 k, 
# 쿠폰 번호 c
N, d, k, c = map(int, input().split())

sushi_belt = []
for _ in range(N):
    sushi_belt.append(int(input()))
    
answer = 0

# 맨 왼쪽 값을 쉽게 제거하기 위해 윈도우를 deque로 생성
window = deque()
# 맨 왼쪽의 연속된 값 k-1개로 초기화
for i in range(k-1):
    window.append(sushi_belt[i])

# 윈도우의 맨 왼쪽 포인터
left = 0
# 윈도우의 맨 오른쪽 포인터
right = left + k - 1
# 맨 왼쪽이 N-1까지 오면 반복문 종료
while left < N:
    # 윈도우의 맨 오른쪽에 배치되는 값(right 값)을 추가
    # 스시가 이어져서 접근해야 하기 때문에 N으로 나눈 나머지 값을 사용
    window.append(sushi_belt[right%N])
    # 윈도우 안의 스시의 종류가 몇 개인지 계산
    kind_num = len(set(window))
    # 쿠폰으로 먹을 수 있는 스시가 윈도우 안에 있는 게 아니라면
    if c not in window:
        # 쿠폰으로 먹을 종류를 카운트에 추가
        kind_num += 1
    # 현재 answer보다 큰 값이면
    if answer < kind_num:
        # answer 업데이트
        answer = kind_num

		# 윈도우의 left 값을 제거
    window.popleft()
    # 윈도우 오른쪽으로 한 칸씩 슬라이딩
    left += 1
    right += 1

print(answer)

• 새로 들어오는 right 값은 스시 리스트에서 right % N에 접근해서 가져오고, 제거되는 left 값은 popleft 함수를 사용해서 반복합니다.
• 반복할 때마다 left와 right 모두 +1 << 투포인터와 슬라이딩 윈도우의 차이점

이상입니다.