[Baekjoon] 15961. 회전초밥(Gold 4)[Python]

15961번: 회전 초밥

 

문제

1. 벨트의 임의의 한 위치부터 k개의 접시를 연속해서 먹을 경우 할인된 정액 가격으로 제공합니다.

2. 각 고객에게 초밥의 종류 하나가 쓰인 쿠폰을 발행하고, 1번 행사에 참가할 경우 이 쿠폰에 적혀진 종류의 초밥 하나를 추가로 무료로 제공합니다. 만약 이 번호에 적혀진 초밥이 현재 벨트 위에 없을 경우, 요리사가 새로 만들어 손님에게 제공합니다.

 

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

 

풀이

크기가 k로 정해진 슬라이드 윈도우를 하나씩 이동시키면서 먹을 수 있는 초밥 종류의 개수를 구하는 문제입니다.

그럼 중복되는 초밥 종류를 어떻게 구별할 수 있을까요?

 

저는 초밥종류의 개수가 많지 않기 때문에 배열을 이용하였습니다.

chobab = [0 for _ in range(d+1)]

슬라이드 윈도우가 이동할 때 초밥의 종류에 맞는 index를 1 증가시켜주고, 반대로 제외된 초밥 종류의 맞는 index를 1 감소 시켜줍니다.

 

이 때, index의 값이 1이면 새로 추가된 종류이고 값이 0이면 제외된 종류이기 때문에

먹을 수 있는 초밥종류 개수를 저장하고 있는 변수에서 적절하게 값을 빼고 더해줄 필요가 있습니다.

 

이는 아래와 같이 구현하였습니다.

# start꺼 제외
chobab[belt[i]] -= 1
# 해당 종류가 슬라이드 윈도우에 포함되어 있지 않은 경우
if chobab[belt[i]] == 0: number -= 1

# end꺼 추가
chobab[belt[(i+k)%N]] += 1
# 해당 종류가 슬라이드 윈도우에 새로 포함되는 경우
if chobab[belt[(i+k)%N]] == 1: number += 1

 

이제 저희가 가지고 있는 쿠폰만 처리하면 됩니다.

쿠폰에 해당하는 index의 값이 0인 경우, 해당 초밥종류를 먹지 않았다는 의미이므로 number에 1를 추가해주고

만약 1 이상인 경우, 이미 먹은 초밥 종류라는 의미이므로 그대로 number를 사용해주면 됩니다. 😊👍

answer = max(answer, number + (1 if chobab[c] == 0 else 0))

 

코드

import sys
input = sys.stdin.readline

N, d, k, c = map(int, input().split())
belt = [int(input()) for _ in range(N)]

# 각 초밥 종류 별 개수
chobab = [0 for _ in range(d+1)]

answer = 0
for i in range(k):
  chobab[belt[i]] += 1
  if chobab[belt[i]] == 1:
    answer+=1
number = answer

if chobab[c] == 0:
  answer+=1

for i in range(0,N):
  # start꺼 제외
  chobab[belt[i]] -= 1
  if chobab[belt[i]] == 0: number -= 1
  # end꺼 추가
  chobab[belt[(i+k)%N]] += 1
  if chobab[belt[(i+k)%N]] == 1: number += 1

  answer = max(answer, number + (1 if chobab[c] == 0 else 0))

print(answer)