[백준] 28107 : 회전초밥 (Python)

 

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

 

 

---

 

아이디어

해당 문제는 결론부터 말하자면, 우선순위 큐(heap) 유형으로 구분할 수 있다. 그러한 이유를 자세히 살펴보자. 먼저, 핵심 요구사항들을 파악하는 것부터 시작해보자.

'1번 손님부터 순서대로 초밥을 먹는다.'

여러 명이 같은 초밥을 시켰을 때, 가장 번호가 낮은 손님이 우선권을 갖는다.

'각 손님은 자신의 주문 목록에 적힌 순서와 상관없이, 초밥이 존재하면 반드시 먹는다.'

주문 목록에 적힌 순서대로 먹는 것이 아닌, 초밥을 기입했냐 안했냐인 존재 여부만을 따진다.

'각 종류의 초밥을 한번만 먹는다.'

한 손님이 같은 초밥을 여러 개 시킬 일은 존재하지 않는다. (중복 x)

 

우선권이라는 인사이트를 파악했다면, 사실 우선순위 큐를 바로 적용할 수 있다. 물론 해당 문제의 풀이 방법은 여러 가지가 존재하지만, 이 문제의 경우에서는 시간 초과와 메모리 초과가 나온다. 그렇기에, 어떤 방식들이 있고, 왜 시간/메모리 초과가 나올 수 밖에 없는지 살펴보자.

예제 입력 1 케이스를 통해 분석해보자.

 

예시를 통한 알고리즘 탐색

완전 탐색

다음의 사진을 보자.

문제 풀이 과정.

해당 손님의 번호가 배열의 인덱스를 나타내고, 값은 해당 손님이 주문한 목록 배열이 된다. 다시 말해, 2차원 배열을 arr이라 한다면, arr[1]=[1,6]으로 표현한다. 이는 '1번 손님은 1번 초밥과 2번 초밥을 주문했다'라는 의미이다.

요리사가 초밥을 방출할 때의 파란색 글씨를 살펴보자. 각 해당 손님의 주문 리스트를 for문을 통해 완전 탐색을 진행한다. 즉, 각 손님이 주문 목록의 원소들을 모두 탐색하는 방식이다.

손님은 N명, 주문 목록의 원소 수는 K, 요리사의 방출 초밥 개수는 M개이다. 각 M에 대해 각 손님 N명의 주문 목록의 원소 K를 탐색해야하므로, 시간 복잡도는 O(m*n*k)가 된다. 즉 이는 O(n*n*n)에 가깝다. 문제에서 주어지는 각 파라미터의 입력 범위는 10만 20만 단위이므로, 완전 탐색은 시간 초과의 결과로 이어지게 된다.

 

완전 탐색 - 주문 목록 탐색 최적화

완전 탐색에서 주문 목록 자료구조 변경

위의 완전 탐색과 다르게 주문 목록 배열을 변경하여 최적화를 진행하였다. 다음과 같이 변경 사항을 정리할 수 있다.

• 기존 ADT
  • order_list=[1, 3, 5, ...]
  • order_list[1] = 3번 초밥
• 변경 ADT
  • order_list=[_, 1, 0, 0, ...]
  • order_list[1] = 1개

차이를 알겠는가? 인덱스를 기존 넘버링에서 초밥의 종류 번호로 변경이 되었고, 값은 해당 초밥 종류 번호를 몇개 시켰느냐로 바뀐 것이다. 이를 통해, 각 손님이 해당 초밥을 시켰는지 탐색하는 과정을 O(1)로 최적화한 것이다.

이를 바탕으로, O(m*n)까지 시간을 줄일 수 있다. 그러나, 주문목록 배열의 크기가 각 손님들마다 최대 20만까지 가능하므로, 메모리 최대 공간 크기는 20만*손님수 만큼 될 것이다. 그러므로, 이 방식은 메모리 초과로 이어지게 될 가능성이 높다.

---

여기까지 핵심 문제점들을 정리해보자면, 다음과 같다.

1. 각 손님의 주문 목록을 어떻게 빨리 조회할 수 있는가
2. 20만의 배열 크기로 저장하는 것이 아닌, 필요수만큼 저장하는 방식은 어떤게 있는가
3. 우선권을 가진 손님부터 어떻게 조회해야 할까

이 문제점들을 모두 해결가능한 기법이 우선순위 큐이다.

 

우선순위 큐 - 최소힙

요구사항에서 우선권이라는 인사이트를 통해, 다음과 같이 생각해볼 수 있다.

'같은 초밥을 여러명이 주문 시, 더 빠른 손님의 ID는 누구인가?'

다음의 사진을 보자.

최소힙을 통한 자료 구조 설정

초밥 종류를 원소로 갖는 전역 배열을 설정하고, 각 인덱스에 해당되는 값에 최소힙을 배치시킨다. 해당 최소힙에는 손님 번호를 삽입하면 된다. 예를 들어, 다음과 같은 표현으로 해석이 가능하다.

• ex) order_lists[1] = min_heap[1,3,5]
  • 1번 초밥(order_lists의 1번째 원소)을 주문한 사람들의 목록(최소힙)에는 1번손님,3번손님,5번손님(최소힙 원소)이 저장되있다. 
  • 최소힙 성질에 따라, Root 노드가 가장 작은 번호를 가지므로, 가장 먼저 받는 사람은 1번 손님이다.

초밥 종류 조회는 order_list[i]로 할 수 있으므로 O(1)이고, 해당 초밥을 받는 사람 조회도 O(1)이다. 여기에 최소힙 pop 이후 재정렬 시 O(log n)이 소요된다. 즉, O(m * log n)으로 표현 가능하다. 그러므로, 각 최소힙의 root 노드들만을 비교하여 정답을 카운팅하면, 제한된 시간과 메모리 안으로 통과가 가능하다. 

그럼에도 설명이 부족함을 느낀다면, 아래 '정답 코드' 카테고리에서 보충 가능하다. 코드에 주석을 달아놓았다.

 

정답 코드

# https://www.acmicpc.net/problem/28107
# 회전초밥
# 큐,우선순위 큐

input=__import__('sys').stdin.readline
import heapq

n,m=map(int,input().split())
order_lists=[[] for _ in range(200001)] # 초밥종류 리스트. 각 원소는 주문한 손님 최소힙

# 손님 ID 확인 및 주문한 초밥 최소힙에 삽입
for id in range(n):
    for order in [*map(int,input().split())][1:]:
        heapq.heappush(order_lists[order],id+1)

answer=[0]*(n+1)
# 요리사 초밥 방출
for cur_sushi in [*map(int,input().split())]:
    # 해당 초밥을 누군가가 시켰다면
    try:
        cur_id=heapq.heappop(order_lists[cur_sushi])
        answer[cur_id]+=1
    # 아무도 초밥을 시키지 않았다면
    except:
        continue
    
print(*answer[1:])