99클럽 코테 스터디 파이썬 비기너 20일차 회전초밥

🤔 문제

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

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

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

입력
첫 번째 줄에 손님의 수 $N$과 초밥의 수 $M$이 공백으로 구분되어 주어진다.($1\le N\le 100\ 000; 1\leq M\leq 200\, 000$)

두 번째 줄부터 $N$개의 줄에 걸쳐 각 손님에 대한 주문 목록을 나타내는 정수 $k$와 $A_1,A_2,\ldots, A_k$가 공백으로 구분되어 순서대로 주어진다. $k$는 주문 목록에 적힌 초밥 종류의 개수이며, $A_i$는 주문 목록에 적힌 초밥 종류이다.

($1\leq A_i\leq 200\, 000$)

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

 
$N+2$번째 줄에 요리되는 초밥의 종류를 나타내는 $M$개의 정수 $B_1,B_2,\ldots, B_M$이 공백으로 구분되어 순서대로 주어진다.

($1\leq B_i\leq 200\, 000$)

출력
한 줄에 $N$개의 정수 $C_1,C_2,\ldots C_N$을 공백으로 구분하여 출력한다. $C_i$는 $i$번 손님이 먹은 초밥의 개수를 의미한다.

예제 입력 1

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

 

예제 출력 1

1 3 0

먼저 2번 손님이 3번 초밥과 2번 초밥을 먹는다. 이후, 1번 초밥이 제공되는데 1번 손님이 먼저 이를 먹기 때문에 3번 손님은 본인의 선호 목록에 1번 초밥이 있어도 이를 먹지 못한다. 이후 4번 초밥이 들어오는데 선호 목록에 4번 초밥이 있는 손님이 없으므로 바로 버려진다. 마지막으로 2번 손님이 5번 초밥을 먹게 된다.

따라서 1번 손님은 1개, 2번 손님은 3개, 3번 손님은 0개의 초밥을 먹게 된다.

출처
University > POSTECH > 2023 POSTECH Programming Contest > Contest K번
University > POSTECH > 2023 POSTECH Programming Contest > Open Contest K번

알고리즘 분류
자료 구조, 우선순위 큐, 큐

From Baekjoon, https://www.acmicpc.net/problem/28107

✨ 답안

import sys
import heapq

# 0. Init
sushi = []
customers = {} ## (key: sushi type, value: min-heap of customer numbers)

# 1. Get counts
ccnt, scnt = sys.stdin.readline().strip().split()
ccnt, scnt = int(ccnt), int(scnt)

# 0. Init
answer = [0 for _ in range(ccnt)]

# 2. Get customers' preferred menu
for i in range(ccnt):
    tmpList = sys.stdin.readline().strip().split()
    tmpList.pop(0)  ## Remove the first value - not in use

    for tmp in tmpList:
        if tmp not in customers:
            customers[tmp] = []  ## Initialize min-heap for this sushi type
        heapq.heappush(customers[tmp], i)  ## Store customer number as a min-heap

# 3. Get prepared sushi list
sushi = sys.stdin.readline().strip().split()

# 4. Process
for su in sushi:
    # 4-1. "Is anyone want to have this sushi?"
    if su in customers and customers[su]:  ## Check if this sushi has any waiting customers
        result = heapq.heappop(customers[su])  ## Get the customer with the smallest number
        answer[result] += 1  ## Increase their count

# 5. Output results
sys.stdout.write('\n'.join(map(str, answer)) + '\n')

✨ 원리

1. 스시를 저장할 배열과 고객 정보를 담을 딕셔너리를 생성한다.
2. 카운트를 셀 배열을 생성한다.
3. 고객의 정보를 받아 활용, 딕셔너리가 초밥의 번호 : [ 고객의 번호 (1), 고객의 번호 (2) ] 형태의 값을 저장하도록 한다. 이때, 힙 푸시 함수를 통해 딕셔너리에 저장되는 밸류의 배열이 힙이 되도록 만든다.
4. 준비된 초밥의 번호와 일치하는 번호의 키가 있고, 그 키에 붙은 힙에 고객이 한 명이라도 있다면, 가장 작은 고객의 번호를 뽑고, 초밥을 먹은 횟수를 센다.

💻 구현

• 딕셔너리의 밸류도 리스트가 될 수 있고, 힙이 될 수 있다. 딕셔너리에도 힙 연산을 사용할 수 있기 때문이다. 딕셔너리의 힙 푸시를 하는 방법을 잘 보아두자. ' heapq.heappush(customers[tmp], i) ', 원래 리스트의 이름이 들어갈 자리에 딕셔너리와 키 값을 넣어준다는 데 주의하자.
• ' customers[tmp] = [] ', 이렇게 하면 딕셔너리에 새 키를 넣고 값을 할당하는 게 아니라 배열을 할당할 수 있다.

😥 오류

• 결과는 적절히 출력되는 코드를 작성했는데, 도무지 시간 초과 문제를 해결할 묘책이 생각나지 않았다. 그래서 인공지능의 힘을 빌렸다. 오늘은 이미 아침부터 너무 과로했다. 필기 시험을 치고, 아르바이트 대타를 갔다가, 대청소를 한 채, 내일 시험을 기다리며 17시간 째 깨어있다. 오늘은 학습에 초점을 둔다..
• 문제가 발생한 코드는 아래와 같은데, 힙은 최대와 최소 값을 뽑아내는 데 장점이 있지, 탐색에는 효율이 좋지 못하다. 이것은 전적으로 우선순위 큐를 이용했던 내 초기 답안이다. 이미 시간 복잡도는 파트 2에서 O(n^2logn), 파트 4에서 O(n^2)이다.

import sys
import heapq

# 0. Init
sushi = [] ## String, an arry
customers = [] ## String, a heap

# 1. Get counts
ccnt, scnt = sys.stdin.readline().strip().split()
ccnt, scnt = int(ccnt), int(scnt)

# 0. Init
answer = [0 for i in range(ccnt)]

# 2. Get customers' preferred menu -> Time over
for i in range(ccnt):
    tmpList = []
    tmpList = sys.stdin.readline().strip().split()

    # 2-1. Make tuples
    tmpList.pop(0) ## Remove the first value - not in use
    for tmp in tmpList: 
        heapq.heappush(customers, (str(i), tmp)) ## No return value, no list comprehension

# 3. Get prepared sushi list
sushi = sys.stdin.readline().strip().split()

# 4. Process
for su in sushi:
    # 4-1. "Is anyone want to have this sushi?" -> Time over
    filtered = list(filter(lambda tup: tup[1] == su, customers))

    # 4-2. Get the first customer, even there are two or more candidates, and count
    if filtered:
        result = filtered.pop(0)[0]
        answer[int(result)] += 1

• 탐색 시에는 오늘의 정답과 같이 키 변환을 통해 O(1)로 접근이 가능한 딕셔너리를 사용하도록 하자.

😂 후기

모든 코드를 작성한 후 디버깅 작업에 들어가던 전과 달리, 오늘은 매 단위(넘버링 된 입력, 처리 등)마다 디버깅을 했더니 완성 자체는 시간 내에 되었다. 십 분 넘게 문제를 이해하고 있었는데도 말이다. 어디서 문제가 발생한 건지 헤맬 필요도 없고, 나쁘지 않은 방법일지도. (한 단계가 완료돼야 다음 단계로 넘어가는 폭포수 모형 같다.) 그래도 오늘 문제는 결국 내 힘으로 못 푼 거나 마찬가지이다. 결국 이해하기는 했고, 새로운 개념을 공부하기도 했지만 마음에 들지 않는다. 내일 시험까지만 치면 더 집중할 수 있겠지. 역시 필기 시험이 실력을 보장하지는 못한다..