[백준/python/1202] 보석도둑

문제링크 : 보석도둑

최대한 비싼 보석을 훔치는 방법을 찾는 문제이다.
heapq는 자동으로 정렬이 되는 효과가 있기 때문에 정렬이 시간초과가 날 경우 유용하게 사용할 수 있다.

import sys
import heapq

input=sys.stdin.readline
n,k=map(int, input().split())
jew=[list(map(int, input().split()))for _ in range(n)]
bag=[int(input())for _ in range(k)]
jew.sort()
bag.sort()

total=0
temp=[]
for b in bag: #bag의 최솟값부터
    while jew and b>=jew[0][0]:
        heapq.heappush(temp, -jew[0][1])
        heapq.heappop(jew)
    if temp:
        total+=heapq.heappop(temp)
    elif not jew:
        break
print(-total)

heap은 작은 값이 부모노드로 큰 값이 자식노드로 들어간다.
heappop을 사용할 경우 root값이 빠져나온다(가장 작은 값)

정말 좋은 기술인데 왜 항상 떠오르지 않을까!!!