보석 도둑 - 1202번

백준에서는 파이썬 모듈인 queue모듈을 사용할 수 없다.(이 모듈안에 우선순위큐 모듈이 있다.)

따라서 max heap을 이용하여 풀었다.

보석들은 무게가 작은 순으로, 가방은 적게 담을 수 있는 가방 순으로 정렬을 한다.

가방을 한개씩 검사한다. 

while 무한루프를 통해 보석을 하나씩 뺀다. 이때, 보석의 무게가 가방의 무게를 넘지 않도록 한다.

만약 while이 정지하면 앞에서 하나씩 뺐던 보석들을 max heap으로 담아둔 heap에서 root위치에 있는 값을 결과 변수에 pop하여 더해준다.

만약 더이상 뺄 보석이 없으면 중지한다.

 

문제를 풀 때, 답은 맞았는데 시간초과와 런타임에러가 많이 떠서 코드의 구조를 갈아엎어가면서 새로운 구조를 만들어 갔다.

무한루프로 하나씩 꺼내서 담아두는 방식을 생각하는 것이 가장 힘들었던것 같다. 결국 다른 사람들의 풀이에 도움받았다.

import heapq
import sys
n, k = map(int, sys.stdin.readline().split())

price_max_heap = []
bag = []


for _ in range(n):
    m,v = map(int, sys.stdin.readline().split())
    heapq.heappush(price_max_heap, (m,v))

for _ in range(k):
    heapq.heappush(bag,int(sys.stdin.readline()))

bag.sort()
valuable = []
result = 0

for i in bag:
    while price_max_heap and price_max_heap[0][0] <= i:
        heapq.heappush(valuable,-1*heapq.heappop(price_max_heap)[1])
    if valuable:
            result -= heapq.heappop(valuable)
            n-=1
    elif price_max_heap == False:
        break
    
print(result)