[BOJ][⚪2][백준#01927] 최소 힙

문제 출처

BAEKJOON Online Judge #1927

문제

널리 잘 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.

배열에 자연수 x를 넣는다. 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

입력

첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. x는 231보다 작은 자연수 또는 0이고, 음의 정수는 입력으로 주어지지 않는다.

출력

입력에서 0이 주어진 횟수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다.

예제

입력

9
0
12345678
1
2
0
0
0
0
32

출력

0
1
2
12345678
0

My Sol

import sys
input = sys.stdin.readline

def enq(n):
    global last, arr
    last += 1
    arr[last] = n
    c = last
    p = last//2

    while p and arr[c] < arr[p]:
        arr[c], arr[p] = arr[p], arr[c]
        c = p
        p = c//2

def deq():
    global last, arr
    ret = arr[1]
    arr[1] = arr[last]
    last -= 1

    p = 1
    c = 2
    while c <= last:
        if c+1 <= last and arr[c+1] < arr[c]:
            c += 1

        if arr[c] < arr[p]:
            arr[c], arr[p] = arr[p], arr[c]
            p = c
            c = p*2

        else:
            break

    print(ret)


arr = [0]*100001
last = 0
N = int(input())
for _ in range(N):
    n = int(input())

    if n:
        enq(n)
    else:
        if last > 0:
            deq()
        else:
            print(0)
            continue

최대 힙과 반대로, 자식 노드가 부모 노드보다 값이 작으면 부모 노드와 교환해주는 방식이다. 로직 자체는 같으므로 어렵지 않게 풀 수 있었다.

결과

맞았습니다!!

모범답안

출처

import heapq
from sys import stdin

T = int(stdin.readline().rstrip())

heap = []
for _ in range(T):
    order = int(stdin.readline().rstrip())
    if order == 0:
        if not heap:
            print(0)
        else:
            print(heapq.heappop(heap))
    else:
        heapq.heappush(heap, order)

역시 heapq 라이브러리를 이용해 풀었다.

• pop: heappop(heap) - heap으로 지정한 배열을 heappop() 안에 넣음
• push: heappush(heap, n) - 첫 인자로 heap, 두 번째 인자로 넣을 값 n을 넣음
• heappush에서 넣을 값에 - 부호를 붙이면 최대 힙, 아니라면 최소 힙