[BOJ][⚪2][백준#11279] 최대 힙

문제 출처

BAEKJOON Online Judge #11279

문제

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

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

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

입력

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

출력

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

예제

입력

13
0
1
2
0
0
3
2
1
0
0
0
0
0

출력

0
2
1
3
2
1
0
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[p] < arr[c]:
        arr[p], arr[c] = arr[c], arr[p]
        c = p
        p = c//2
    

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

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

        if arr[c] > arr[p]:
            arr[c], arr[p] = arr[p], arr[c]
            p = c
            c = 2*p
        else:
            break

    print(tmp)


N = int(input())
last = 0
arr = [0]*100002

for _ in range(N):
    n = int(input())
    if n:
        enq(n)
    else:
        if last > 0:
            deq()
        else:
            print(0)
            continue

최대 힙을 이용하는 문제였다. 완전 이진 트리에서 1번 노드에 최댓값을 위치시키고 넣고 빼는 과정과 함께 정렬하는 알고리즘을 작성하였다.

결과

맞았습니다!!

deq 부분에서 경계값 설정 및 오른쪽 왼쪽 자식 노드의 선택을 하는 알고리즘이 헷갈렸기 때문에 이 부분을 다시 짚고 넘어가야겠다.

모범답안

출처

import sys, heapq
inp = sys.stdin.readline

n = int(input())
h = []
for i in range(n) :
    x = int(inp().strip())
    if not x :
        if h :
            print(-heapq.heappop(h))
        else :
            print(0)
    else :
        heapq.heappush(h, -x)

많은 사람들이 heapq 라이브러리를 사용해서 문제를 해결하였다.