[백준][Python]1202번(보석 도둑)

백준 1202번

✔️ 문제 풀이

◾heapq 활용

• heapq는 가장 작은 원소가 루트에 오도록 보장하는 자료구조이다.
• 원소가 추가되거나 삭제될 때마다 heapify를 통해 자료를 정렬하여 루트에 최소값이 오도록 한다.
• 보석의 무게와 가치를 입력받고, 이를 jewels에 heappush한다.
  ⇒ heappop할 때마다 최소값을 보장받을 수 있다.
• 가방을 bags에 입력받고 오름차순으로 정렬한다.
• 가방을 기준으로 반복문을 돌리면서 가방에 담을 수 있는 보석의 가치를 max_jewels에 heappush한다.
  ⇒ 이때 저장하는 원소를 음수로 저장하여, 최대값이 루트에 올 수 있도록 한다.
  (꺼내고 나서 다시 부호를 바꿔주면 됨)
• 이번 bag이 jewels에서 더 이상 담을 수 있는 보석이 없으면 max_jewels에서 값을 heappop하여 이 가방이 담을 수 있는 보석 중 가장 큰 보석을 담는다.
• 한 번 탐색한 보석은 jewels에서 pop되기 때문에 다음 가방에서 jewels를 탐색할 때 시간을 줄일 수 있다.

최종 제출 코드

import heapq
import sys
input = sys.stdin.readline

j, b = map(int, input().split())
jewels = []
for i in range(j):
  heapq.heappush(jewels, list(map(int, input().split())))

bags = []
for i in range(b):
  bags.append(int(input().rstrip()))
bags.sort()

ans = 0
max_jewels = []

for bag in bags:
  while jewels and bag >= jewels[0][0]:
    heapq.heappush(max_jewels, -heapq.heappop(jewels)[1])

  if max_jewels:
    ans += (-heapq.heappop(max_jewels))

print(ans)