[백준] 1202번 보석도둑 - 우선순위큐 파이썬

 

1202번: 보석 도둑

 

문제 접근 방법

1. 최대 가격을 구하는 것이므로 바구니에 들어가면서 가격이 제일 비싼 보석을 찾아야한다. 처음에는 바구니를 N번 돌며 해당하는 보석의 후보군을 모두 찾고 후보군에서 전체를 탐색하며 가장 가격이 비싼 보속을 찾아야한다고 생각했지만 우선순위 큐를 사용해서 시간을 줄일 수 있다.

2. 담을 수 있는 무게가 작은 바구니부터 순회를 시작해야한다. 그래야 모든 보석을 순차적으로 빠짐없이 후보에 넣을 수 있어서.

3. 보석도 무게를 작은 것부터 오름차순으로 정렬하기.

 

우선순위큐

우선순위 큐는 순위가 우선되는 것부터 뽑아쓸때 사용하는 자료 구조이다. 리스트와 힙으로 구현할 수 있다.

우선순위 큐 참고 영상 : https://www.youtube.com/watch?v=AjFlp951nz0

 

힙으로 우선수위 큐를 구현하면 삽입, 삭제는 O(logN)이 걸리고 N개의 데이터를 모두 삽입하고 꺼내면 N*logN이 각각 소요되는데 BigO 표기법에 따라 N*logN이 소요된다.

 

최종 제출코드

import heapq
import sys
input=sys.stdin.readline
N, K = map(int, input().split())
j_list = [list(map(int, input().split())) for _ in range(N)]
b_list = [int(input()) for _ in range(K)]
j_list.sort()
b_list.sort()
hq = []
result = 0
for b in b_list:
  while j_list:
    if j_list[0][0] <= b:
      heapq.heappush(hq, -j_list[0][1])
      heapq.heappop(j_list)
    else:
      break
  if hq:      
    selected = heapq.heappop(hq)
    result += -selected
print(result)

 

 

현재 바구니에 넣을 수 있는 보석을 찾아 최대힙에 넣는다. NlogN

가장 큰 가격 즉 root node에 있는 값을 가져온다. N(1)

이렇게 해도 시간초과가 발생헀는데 sys.stdin.readline을 넣어줘서 해결했다.