[Python] 백준/BOJ 28107번: 회전초밥

28107: 회전초밥 (Silver 1)

https://www.acmicpc.net/problem/28107

---

문제

회전 초밥 가게에 N명의 손님이 있고, 요리사는 M개의 초밥을 순서대로 만든다. 요리사가 초밥을 만들 경우, 1번 손님부터 N번 손님의 순서대로 그 초밥을 받게 된다. 만약 먼저 초밥을 받는 손님이 초밥을 먹을 경우, 뒤의 손님들은 해당 초밥을 먹을 수 없다. 만약 아무도 해당 초밥을 먹지 않는다면, 초밥은 버려진다.

N명의 손님은 각자 먹고 싶은 초밥이 적힌 주문 목록을 가지고 있다. 목록에 적힌 초밥의 순서에 상관 없이 만약 목록에 적혀있는 초밥이 앞에 오면 반드시 먹는다. 만약, 목록에 적히지 않은 초밥을 받는다면 그 초밥은 반드시 먹지 않는다. 단, 손님들은 다양한 초밥을 먹고 싶어하기 때문에 각 종류의 초밥은 최대 한 번만 먹는다.

각 손님의 주문 목록과 순서대로 만들어지는 M개의 초밥이 주어질 때, 각 손님이 먹게 되는 초밥의 개수를 구해 보자.

---

Approach(1) - 시간 초과

• 리스트를 사용하여 각 손님의 주문 목록을 저장하고, 요리되는 초밥을 순차적으로 확인하여 해당 초밥이 주문 목록에 있으면 먹은 걸로 처리

n, m = map(int, input().split())
order = []
cnt = [0] * n

for _ in range(n):
    order.append(list(map(int, input().split()[1:])))

menu = list(map(int, input().split()))

for m in menu:
    for i in range(len(order)):
        if m in order[i]:
            cnt[i] += 1
            break

print(*cnt, sep=' ')

---

Approach(2) - 정답

• 시간초과를 해결하기 위해 우선순위 큐로 풀었다
• n개의 라인에서 각 손님이 시킨 초밥 종류를 orders 힙에 담는다
  • 0번 손님이 1, 6 초밥을 주문했다면 orders[1]에 0, orders[6]에 0을 push한다
  • 1번 손님이 2, 3, 5 초밥을 주문했다면 orders[2], orders[3], orders[5]에 1을 push한다
  • 2번 손님이 1 초밥을 주문했다면 orders[1]에 2를 push한다
  • orders 출력 결과: [[], [0, 2], [1], [1], [], [1], [0], ...]
• 완성된 초밥을 menu에 입력 받는다
• menu 안의 sushi를 하나씩 꺼내서 orders[sushi]가 비어있지 않다면
  • 해당 리스트 안의 값을 pop
  • pop한 값을 cnt의 index로 삼아 해당 초밥을 주문한 손님이 먹은 것으로 한다(+1)

---

Code

import heapq
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
orders = [[] for _ in range(200_001)]

for i in range(n):
    k, *items = map(int, input().split())
    for item in items:
        heapq.heappush(orders[item], i)
        
menu = list(map(int, input().split()))
cnt = [0] * n

for sushi in menu:
    if orders[sushi]:
        cnt[heapq.heappop(orders[sushi])] += 1

print(*cnt, sep=' ')