문제

문제 링크 : https://www.acmicpc.net/problem/1927

풀이 - 1

최소 힙과 insert와 delete 함수를 직접 구현한 풀이이다.

최소 힙은 deque를 사용했다.

insert 함수는 우선 삽입하고자 하는 수 x를 deque의 끝에 삽입한 뒤에 부모의 값보다 x가 작지 않을 때까지 x와 부모를 swap 해준다.

delete 함수는 우선 루트 노드와 맨 끝의 노드를 swap 해준 뒤에 deque를 pop 해준다. 이후에 루트 노드의 자식 노드들 중 작은 노드와 루트 노드의 크기를 비교한다. 루트 노드의 크기가 자식 노드의 크기보다 크지 않을 때까지 루트 노드와 자식 노드를 swap 해준다.

from sys import stdin
from collections import deque

n = int(stdin.readline())
heap = deque()
heap.append(-1)

def insert(x):
    heap.append(x)
    idx = len(heap) - 1
    while((idx != 1) and (x < heap[idx // 2])):
        heap[idx], heap[idx//2] = heap[idx//2], heap[idx]
        idx = idx//2

def delete():
    if len(heap) == 1:
        print(0)
        return
    heap.popleft()
    heap[0], heap[len(heap) - 1] = heap[len(heap) - 1], heap[0]
    print(heap.pop())
    heap.appendleft(-1)
    parent = 1
    while True:
        child = parent * 2

        if (child + 1 < len(heap) and heap[child] > heap[child + 1]):
            child += 1
        if (child >= len(heap) or heap[child] > heap[parent]):
            break
        heap[child], heap[parent] = heap[parent], heap[child]
        parent = child

for _ in range(n):
    x = int(stdin.readline())
    if x == 0:
        delete()
    else:
        insert(x)

풀이 - 2

두 번째 풀이는 파이썬의 heapq 모듈을 이용한 풀이이다.

heapq 모듈을 사용할 때 heap은 리스트로 둔다.

x를 힙에 삽입할 때는 heappush 메소드를 사용하면 되고, 힙에서 최솟값을 빼낼 때는 heappop 메소드를 사용하면 된다.

from sys import stdin
import heapq

heap = []
n = int(stdin.readline())

for _ in range(n):
    x = int(stdin.readline())
    if x == 0:
        if len(heap) == 0:
            print(0)
        else:
            print(heapq.heappop(heap))
    else:
        heapq.heappush(heap, x)