[99클럽 코테 스터디] 20일차 TIL - 회전초밥

 

문제 설명

28107번: 회전초밥

 

 

문제

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

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

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

.

입력

첫 번째 줄에 손님의 수 N과 초밥의 수 M이 공백으로 구분되어 주어진다. (1≤N≤100 000;1≤M≤200000)

두 번째 줄부터 N개의 줄에 걸쳐 각 손님에 대한 주문 목록을 나타내는 정수 k와 A1,A2,…,Ak가 공백으로 구분되어 순서대로 주어진다. k는 주문 목록에 적힌 초밥 종류의 개수이며, Ai는 주문 목록에 적힌 초밥 종류이다. (1≤Ai≤200000)

각 손님의 주문 목록에 적힌 초밥 종류는 모두 다르며, 모든 손님에 대해 k의 합이 200000 이하임이 보장된다.

 N+2번째 줄에 요리되는 초밥의 종류를 나타내는 M개의 정수 B1,B2,…,BM이 공백으로 구분되어 순서대로 주어진다. (1≤Bi≤200000)

 

출력

한 줄에 N개의 정수 C1,C2,…CN을 공백으로 구분하여 출력한다. Ci는 i번 손님이 먹은 초밥의 개수를 의미한다.

 

입출력 예 설명
입력 1

3 5
2 1 6
3 2 3 5
1 1
3 2 1 4 5

출력 1 

1 3 0

 

‍💻내가 짠 코드

import sys

def sushi_distribution(N, M, orders, sushi_list):
    customer_orders = []  # 각 손님의 주문 목록
    sushi_map = {}  # 초밥 종류별 주문한 손님 매핑
    eat_count = [0] * N  # 각 손님이 먹은 초밥 개수

    # 손님들의 주문 목록 처리
    for i in range(N):
        order_set = set(orders[i])  # 중복 방지를 위해 set 사용
        customer_orders.append(order_set)
        for sushi in order_set:
            if sushi not in sushi_map:
                sushi_map[sushi] = []
            sushi_map[sushi].append(i)  # 해당 초밥을 주문한 손님 추가

    # 초밥 배분 처리
    for sushi in sushi_list:
        if sushi in sushi_map:
            for customer in sushi_map[sushi]:
                if sushi in customer_orders[customer]:  # 아직 먹지 않은 초밥이라면
                    eat_count[customer] += 1
                    customer_orders[customer].remove(sushi)  # 중복 방지를 위해 제거
                    break  # 초밥은 한 명만 먹을 수 있음
    
    print(" ".join(map(str, eat_count)))

if __name__ == "__main__":
    # 입력 받기
    N, M = map(int, sys.stdin.readline().split())
    orders = [list(map(int, sys.stdin.readline().split()))[1:] for _ in range(N)]
    sushi_list = list(map(int, sys.stdin.readline().split()))
    
    sushi_distribution(N, M, orders, sushi_list)

✍ 접근 방법

• 입력 처리
  • N, M: 손님 수와 초밥 수를 입력받음.
  • orders: 각 손님의 주문 목록을 리스트로 저장.
  • sushi_list: 요리사가 만드는 초밥의 순서를 리스트로 저장.
• 손님별 초밥 주문 저장
  • customer_orders: 각 손님의 주문 목록을 set으로 저장(중복 방지).
  • sushi_map: 특정 초밥을 원하는 손님 리스트를 저장하는 dict(빠른 접근을 위함).
• 초밥을 순서대로 제공하며 배분
  • 요리된 초밥을 sushi_map에서 확인하여 원하는 손님을 찾음.
  • 초밥을 받을 수 있는 가장 빠른 순번의 손님이 먹고 break(뒤의 손님은 못 먹음).
  • 손님이 초밥을 먹으면 해당 초밥을 set에서 제거하여 중복 방지.
• 출력
  • 각 손님이 먹은 초밥 개수를 출력.