[BOJ] 1202 python (우선순위큐 공부)

이 문제도 우선순위 큐 문제였다.

 

우선 v 값을 정렬하여서 max 값을 저장하는 방식으로 풀면 되지 않나

그리고 있다면 v 값에 += 하는 sum 으로 출력하면?

 

우선순위큐로 푸는 문제였다. 

 

우선순위 큐에 대해 잘 설명해주는 강의있어서 참고하고,

기본적인 문법과 사용, 큐의 작동 등을 자세하고 심플하게 알려주어서 도움이 되었다. 

https://www.daleseo.com/python-heapq/   

 

0. 응용으로 힙정렬 구현

 

heap_sort 해주고 인자값으로 nums 받고

돌아가면서 heap 리스트에 num 값 넣어주고

 

while heap:

heap이 0이 될 때까지 반복해주고, heappop 으로 pop된 num들을 append 시켜준다.

 

return 해주면은, 힙 정렬되어서 출력이 됨다.

 

 

1.이 최대힙이 대박이었는데

 

처음에 문제 풀고 - 를 붙여서 출력하면 max heap 으로 나온다, 만 생각했다.

근데 원리가 이거였다.

- 를 붙여도 여전히 min heap 으로 가장 작은 값들이 출력된다, 일반 num 으로 튜플형식으로 push를 해주었으니

num 의 경운, max heap으로 정렬이 된 상태인 것.

 

2. 문제 풀이

import sys
import heapq
input = sys.stdin.readline

n,k=map(int, input().split())

dia = [list(map(int, input().split())) for _ in range(n)]
bag = [int(input()) for _ in range(k)]
dia.sort()
bag.sort()

result=0
temp=[]
for i in bag:
    while dia and i>dia[0][0]:
        heapq.heappush(temp, -dia[0][1])
        heapq.heappop(dia)

    if temp:
        result += heapq.heappop(temp)

print(-result)

dia = [list(map(int, input().split())) for _ in range(n)] 

으로 해서 줄일 수 있고

 

bag = [int(input()) for _ in range(k)]

bag의 경우 한 수만 입력 받으니 map 안 써도 됩니다.

 

if temp:

        result += heapq.heappop(temp)

값이 temp 에 있는 경우는 += 해주세요

 

후에 출력시에는 max heap 값을 출력해주어야 하니, -result 값이니다..

 

 

 

다시 한 번 풀어봐야겠음