백준 1202 파이썬 보석 도둑

import heapq
import sys

N, K = map(int, sys.stdin.readline().split())
jewelryList = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
bagList = [int(sys.stdin.readline()) for _ in range(K)]
jewelryList.sort()
bagList.sort()

result = 0
temp = []

for bagWeight in bagList:
    while jewelryList and bagWeight >= jewelryList[0][0]:
        heapq.heappush(temp, -heapq.heappop(jewelryList)[1])  # Max heap

    if temp:
        result += heapq.heappop(temp)
    elif not jewelryList:
        break

print(-result)

힙은

1. 데이터가 지속적으로 정렬이 되어야 할 때
2. 데이터의 삽입 / 삭제가 빈번히 일어날 때
풀이시간을 많이 줄여줍니다.

 

만약 temp가 비어있는데, 보석리스트까지 비어있다면 종료합니다.
(가방의 개수가 많이 남아있어도 넣을 보석이 없으면 의미가 없습니다.)