[백준(BOJ)] 1927번 최소 힙, 11279번 최대 힙

문제

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

1927번: 최소 힙

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

11279번: 최대 힙

주어진 연산에 따라 배열에 자연수를 추가하거나, 배열에서 가장 작거나 큰 값을 출력하고 제거하는 프로그램을 만드는 문제다.

예시

최소 힙 Example :

Input : 9
	0
	12345678
	1
	2
	0
	0
	0
	0
	32
Output : 0
	1
	2
	12345678
	0

 

최대 힙 Example :

Input : 13
	0
	1
	2
	0
	0
	3
	2
	1
	0
	0
	0
	0
	0
Output : 0
	2
	1
	3
	2
	1
	0
	0

풀이

import heapq
import sys

n = int(sys.stdin.readline())
arr = []

for _ in range(n):
    x = int(sys.stdin.readline())

    if x == 0:
        if arr:
            print(heapq.heappop(arr))
        else:
            print(0)

    else:
        heapq.heappush(arr, x)

 

- heappush()로 자연수 x를 추가하고, heappop()으로 최소 힙에서 가장 작은 값을 출력하고 제거한다.

 

import heapq
import sys

n = int(sys.stdin.readline())
arr = []

for _ in range(n):
    x = int(sys.stdin.readline())

    if x == 0:
        if arr:
            print(-heapq.heappop(arr))
        else:
            print(0)

    else:
        heapq.heappush(arr, -x)

 

- 위에 풀이와 거의 유사하나 최대 힙처럼 활용하기 위해 음수(-x)로 추가하고 가장 큰 값을 출력하고 제거하기 위해 '-'를 추가하여 원래의 값으로 반환한다.