백준23757 - 아이들과 선물 상자 (Heap) python

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

문제에서는 선물의 갯수가 담긴 상자, 아이들이 원하는 선물의 양을 담은 배열이 주어진다. 아이들이 현재 선물이 가장 많이 담겨 있는 상자에서 각자 원하는 만큼 선물을 가져갈 때 모두 각자 원하는 선물을 가져갈 수 있다면 1, 그렇지 않다면 0을 출력하는 문제다.

 

문제 풀이 방식

현재 가장 많은 선물이 담겨 있는 상자를 효율적으로 찾기 위해서는 힙의 구현이 필요했다. python에서는 내장 모듈에서 불러와 사용할 수 있으나, 기본적으로는 최소 힙만 제공하기 때문에, heap에 데이터를 음수로 넣어줌으로써 최대 힙으로의 역할을 가능하게끔 했다.

이후, 힙에 있는 가장 많은 선물을 가지고 있는 상자와 아이가 원하는 선물의 양과 비교한 뒤, 만약 선물의 양보다 아이가 원하는 양이 크다면, 두 값의 차만큼 다시 최대 힙에 추가, 같다면 패스, 작다면 결괏값을 0으로 수정 후 반복문을 종료하는 식으로 마무리를 지었다.

 

전체 소스코드

import sys
data_temp = sys.stdin if sys.platform == 'linux' else open('입력.txt', 'r')
input_data = data_temp.read().splitlines()
from heapq import heappop, heappush

def solution (data) :
  arr = [list(map(int, v.split())) for v in data]
  [_,_],present,children = arr
  
  presentHeap = []
  for p in present :
    heappush(presentHeap, -p)
    
  result = 1
  for c in children :
    box = -heappop(presentHeap)
    if c > box : 
      result = 0
      break
    else :
      if c == box : continue
      heappush(presentHeap, -(box-c))
  
  print(result)
    
solution(input_data)