백준 11279. 최대 힙
TRYS AND INSIGHTS
- python에서 우선순위 큐/힙을 담당하는 라이브러리는
heapq
와queue
의PriorityQueue
가 있는데, 여기서는heapq
를 사용해서 풀었다. heapq
- PriorityQue랑 달리 별개의 자료구조가 아님.
- heapq 모듈의 함수를 호출할 때마다 리스트를 인자로 넘김
heappush
,heappop
:heapify(<list>)
:
# 예시
heap = []
# 삽입
heapq.heappush(heap, 1)
heapq.heappush(heap, 2)
# 삭제
x = heapq.heappop(heap)
print(x)
sys.stdin.readline()
: input() 대신 쓸 수 있음. python에서 입력받을 때sys.stdin.readline
은 필수인 것 같기도 함(이거 해야 시간 초과 에러 안 뜸)
[1번 시도]
sys.stdin.readline()
을 안 써서 시간초과 뜸.
[2번 시도]
PriorityQueue를 썼더니 런타임에러 뜸.
원인: import queue나 PriorityQueue가 안 먹히는 것 같다는 추측성 글이 있음.
SOLUTION
최소 힙이 메인인 heapq에서 어떻게 해야 최대 힙으로 활용할 수 있을 지 고민하면서 구글링하다가 -1을 곱해서 넣으면 최소 힙으로도 최대힙처럼 사용할 수 있다는 것을 깨달음.
즉, 1<2<3<4의 각 요소에 -1을 곱해 주면 -1>-2>-3>-4가 되는 것처럼 최소 힙에 각 요소에 -1을 곱한 것을 넣어주고, 뽑을 때 원상복귀(-1 또 곱하기)해 주면 최대 힙처럼 쓸 수 있다는 것을 알 수 있음!
import heapq
import sys
def main():
N = int(input())
q = []; ans = []
for _ in range(N):
x = int(sys.stdin.readline())
if x == 0:
# 큐에서 rootpop하고 print
if len(q) == 0:
ans.append(0)
else:
ans.append(-1 * heapq.heappop(q))
else:
# 큐에 insert
heapq.heappush(q, -1*x)
for x in ans:
print(x)
main()
여기서 온라인 알고리즘으로 구현했으면 더 좋았을 것 같기도 하지만, print()가 오래 걸린다는 걸 고려했을 때 그냥 이렇게 하는 게 좋을 것 같기도 함. 메모리에 큰 문제만 없다면..
자매품: 최소 힙
최대 힙과 똑같이 풀되, -1 곱하는 부분만 빼면 됨.
Author And Source
이 문제에 관하여(백준 11279. 최대 힙), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@tera_geniel/백준-11279-최대-힙저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)