[파이썬] 백준 1927번, 11279번, 11286번: 최소 힙, 최대 힙, 절대값 힙

https://www.acmicpc.net/problem/1927

1927번: 최소 힙

https://www.acmicpc.net/problem/11279

11279번: 최대 힙

https://www.acmicpc.net/problem/11286

11286번: 절댓값 힙

3문제 모두 파이썬의 heapq를 응용하는 문제입니다.

n = int(input()) 으로는 시간초과가 떠서 int(sys.stdin.readline()) 으로 입력을 받았습니다.

 

최소힙

import heapq
import sys
heap = []
for _ in range(int(input())):
    n = int(sys.stdin.readline())
    if n != 0:
        heapq.heappush(heap, n)
    else:
        if heap:
            print(heapq.heappop(heap))
        else:
            print(0)

n != 0: heappush를 통해 만들어놓은 heap list에 n을 넣어줍니다.

n = 0: heap이 비어있지 않으면 heappop을 통해 최소값을 출력 후 heap에서 빼주고,

비어있으면 0을 그대로 출력합니다.

 

최대힙

import heapq
import sys
heap = []
for _ in range(int(input())):
    n = int(sys.stdin.readline())
    if n != 0:
        heapq.heappush(heap, (-n, n))
    else:
        if heap:
            print(heapq.heappop(heap)[1])
        else:
            print(0)

n != 0: heappush를 통해 heap list에 (-n, n)을 넣어줍니다 (큰 숫자 순으로 넣기 위해).

n = 0: heap이 비어있지 않으면 heappop을 통해 최대값을 출력 후 heap에서 빼주고,

비어있으면 0을 그대로 출력합니다.

최소힙을 구하는 방법이랑 큰 차이가 없습니다.

절대값 힙

import heapq
import sys
heap = []
for _ in range(int(input())):
    n = int(sys.stdin.readline())
    if n != 0:
        heapq.heappush(heap, (abs(n), n))
    else:
        if heap:
            print(heapq.heappop(heap)[1])
        else:
            print(0)

n != 0: heappush를 통해 heap list에 (abs(n), n)을 넣어줍니다 (n이 음수일 시 구분해주기 위해).

n = 0: heap이 비어있지 않으면 heappop을 통해 최소값을 출력 후 heap에서 빼주고,

비어있으면 0을 그대로 출력합니다.