[백준 1927번] 최소 힙(C++ / python)

 

C++ 풀이

C++은 기본적으로 priority_queue를 지원하는데, 이게 default로 max_heap이라서 min_heap을 쓰려면 음수로 넣어주고 빼서 쓸 때 다시 마이너스 붙여줘서 사용해야한다.

#include <bits/stdc++.h>

using namespace std;
priority_queue<int> pq;

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int N; 
    cin >> N;
    for(int i = 0; i< N; i++)
    {
        int tmp;
        cin >> tmp;
        if(tmp == 0)
        {
            if(pq.empty()) {
                cout << "0\n";
            }else{
                cout << -pq.top() <<'\n';
                pq.pop();
            }
        }else{
            pq.push(-tmp);
        }
    }
}

Python 풀이

힙이 배열 구조로 되어있어서 배열 하나 만들어 놓고 사용

import sys
import heapq
input = sys.stdin.readline

N =  int(input().strip())

heap_list = list()
for _ in range(N):
    a = int(input().strip())
    if(a ==0):
        if(len(heap_list)):
            print(heapq.heappop(heap_list))
        else :
            print('0')
    else :
        heapq.heappush(heap_list,a)