[백준] 11286번 절댓값 힙

💡문제접근

• heapq를 사용해서 해결할 수 있었다. 이전 포스팅에 있었던 [[백준] 11279번 최대 힙]과 [[백준] 1927번 최소 힙]에서 다루었던 문제라 수월했다. 약간의 센스가 있으면 더 좋은 문제다.
• 절댓값만을 저장하는 것이 아니라 입력값과 절댓값을 같이 heappush해줘야 한다.

💡코드(메모리 : 39780KB, 시간 : 144ms)

import heapq
import sys
input = sys.stdin.readline

heap = []
N = int(input().strip())
for _ in range(N):
    val = int(input().strip())
    if val != 0:
        heapq.heappush(heap, (abs(val), val))
    else:
        if len(heap) == 0:
            print(0)
        else:
            print(heapq.heappop(heap)[1])

📌 import heapq

• heapq 모듈을 이용하여 힙 자료구조를 만들어 사용할 수 있다. heapq는 내장 모듈이므로 따로 설치가 필요하지 않고 기본적으로 Min-Priority-queue 구조를 가지고 있다.

• import heapq으로 MaxHeap을 구현하는 방법은 두 가지가 있다.
  ①. 값에 단순히 - 부호를 붙여주는 작업만 해줘도 구현 가능

a = [3,5,2,4,1]
testheap = []
for i in a:
    heapq.heappush(testheap, -i)
for i in range(5):
    print(-heapq.heappop(testheap))

②. 튜플을 이용한다. heapq는 튜플의 첫 번째 요소를 기준으로 정렬을 수행한다. 따라서 첫 번째 요소에 - 값, 두 번째 요소에 원래 값을 저장한다.

a = [3,5,2,4,1]
testheap = []
for i in a:
    heapq.heappush(testheap, (-i,i))
for i in range(5):
    print(heapq.heappop(testheap)[1])

💡소요시간 : 7m