[Baekjoon]백준 1927 최소 힙(실버 2) - Python, C++

문제설명

예제

문제를 살펴보면 이전에 풀었던 최대 힙의 반대 문제이다 이때는 파이썬으로 풀이를 작성할 때

import heapq를 선언한 후에 일부러 자연수에 -를 붙여 음수의 값으로 힙에 넣어주었다

하지만 이번 문제는 최소 힙이기 때문에 기존의 코드에서 -만 빼면 정상적으로 동작하는 것을 확인할 수 있다

https://reflesh02.tistory.com/135 

[Baekjoon]백준 11279 최대 힙(실버 2) - Python

해당 코드에서 -만 빼면 정답임을 확인할 수 있다

import sys
import heapq
input = sys.stdin.readline

cnt = int(input())
heap = []
for _ in range(cnt):
    x = int(input())
    if x == 0:
        if heap:
            print(heapq.heappop(heap))
        else:
            print(0)
    else:
        heapq.heappush(heap, x)

저 문제에서는 시간이 없어서 C++로 작성을 못했는데, 이번 코드는 C++로 작성해보았다

찾아보니 C++에서 queue가 이미 STL로 선언되어있다(STL은 C++을 위한 라이브러리이다)

해당 라이브러리에 pop(), push(), empty() 등이 선언되어있기 때문에 이를 활용하였다

처음에는 cout, cin을 사용하여 코드를 작성하였는데, 시간초과가 발생하여서

ios::sync_with_stdio(false);와 cin.tie(NULL);, cout.tie(NULL);을 추가적으로 작성하였다

그럼에도 불구하고 시간초과가 발생하였고, 그래서 이전에 사용하였던 방식으로 

printf, scanf를 사용하였더니 시간초과를 해결할 수 있었다

#include <iostream>
#include <queue>
using namespace std;

int main() {
    priority_queue<int, vector<int>, greater<int>> heap;
    int cnt;

    cin >> cnt;
    for(int i = 0; i < cnt; i++) {
        int num;
        scanf("%d", &num);
        if(num == 0) {
            if(heap.empty())
                printf("0\n");
            else {
                printf("%d\n", heap.top());
                heap.pop();
            }
        } else {
            heap.push(num);
        }
    }

    return 0;
}