[파이썬/python] 백준 23757 - 아이들과 선물 상자

문제

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

---

문제 설명

1.   N개의 선물을 M명의 아이들에게 나누어주어야 한다.
2. 아이들은 1부터 M까지 고유의 번호를 부여받는다.
   1. 1번 아이부터 M번 아이까지 한 번에 한 명씩 현재 선물이 가장 많이 담겨있는 상자에서 원하는 만큼 선물을 가져갈 수 있다.
   2. 누군가 선물을 가져간 상자에서 또 가져가도 상관없다.
3. 모든 아이가 원하는 만큼의 선물을 가져갈 수 있으면 1, 가져갈 수 없으면 0을 출력한다.

 

---

풀이

아이들에게 1부터 M까지 고유의 번호가 존재하며, 1번 아이부터 순차적으로 가장 많이 담겨있는 상자에서 가져가므로

최대힙을 통해 가장 큰 상자를 순차적으로 꺼내어 아이들에게 나누어 준다.

1. 선물 배열을 입력받은 후 최대힙으로 변환한다.
2. 최대힙에서 선물을 한 개씩 꺼내며, 아이들에게 나누어주고, 남은 선물은 다시 gifts배열에 넣는다.
   1. 만약 가장 크기가 큰 선물상자를 꺼내었을 때, 아이가 원하는 선물보다 작다면 0을 출력한다.
3. 모든 아이들에게 선물을 나누어 줬다면 1을 출력한다.

 

 

---

코드

import sys
import heapq
input = sys.stdin.readline

def max_heap(arr):
    hq = []
    for i in arr:
        heapq.heappush(hq,-i)
    return hq


N,M = map(int,input().split())
gifts = max_heap(list(map(int,input().split())))    
wants = list(map(int,input().split()))


for want in wants:
    gift = -heapq.heappop(gifts)
    if gift < want:
        print(0)
        exit()
    gift -= want
    heapq.heappush(gifts,-gift)
print(1)

---

시간복잡도

• heapq의 삽입, 삭제의 시간복잡도는 $O(logN)$이다.
• 최악의 경우는 모든 아이들이 선물을 가져갈 때 이므로 $O(MlogN)$의 시간복잡도가 소요된다.
• 최악의 경우 $M = 10^5$이므로 약 $O(10^5 * log{10^5}) = O(10^6)$ 으로 시간복잡도가 소요된다.