[파이썬]1202-보석도둑-백준-G2

"""
 *packageName    : 
 * fileName       : 1202_보석_도둑_G2
 * author         : ipeac
 * date           : 2022-03-27
 * description    :
 * ===========================================================
 * DATE              AUTHOR             NOTE
 * -----------------------------------------------------------
 * 2022-03-27        ipeac       최초 생성
 """
import heapq
import sys


def Solution(jew_list, max_weight_list):
      max_weight_list.sort()
      jew_list.sort()
      print("max_weight_list : %s " % max_weight_list)
      print("jew_list : %s " % jew_list)
      
      res = 0
      
      temp = []
      
      for bag in max_weight_list:
            while jew_list and bag >= jew_list[0][0]:
                  heapq.heappush(temp, -jew_list[0][1])
                  heapq.heappop(jew_list)
            
            if temp:
                  res += heapq.heappop(temp)
            elif not jew_list:
                  break
      print(-res)


# Solution(2, 1, [[5, 10], [100, 100]], [11])
# Solution(3, 2, [[1, 65], [5, 23], [2, 99]], [10, 2])
# Solution(2, 2, [[5, 5], [5, 5]], [1, 10])

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

jew_list = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
max_weight_list = [int(sys.stdin.readline()) for _ in range(k)]
Solution(jew_list, max_weight_list)

- 최대힙 문제였다

- 단순 반복문 사용하는 경우 시간초과가 발생한다

- temp 배열안에 해당 가방의 크기가 작은 순으로 비교하여 가방의 가격을 담는다(음수값으로 < 파이썬은 기본 min heap 구조> )

- 담은 후 해당 값 중에 제일 작은 값을 res에 더함. 해당 값을 다시 양수로 전환한다면 정답