[백준] 1927.cpp : 최소 힙

www.acmicpc.net/problem/1927

1927번: 최소 힙

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

int main(void)
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    
    int n;
    cin >> n;
    priority_queue<int, vector<int>, greater<int>> pq;
    for(int i = 0 , data ; i < n ; i++)
    {
        cin >> data;
        if(data == 0)
        {
            if(pq.empty()) cout << 0 << '\n';
            else
            {
                cout << pq.top() << '\n';
                pq.pop();
            }
        }
        else
        {
            pq.push(data);
        }
    }
}

 

[Approach]

1. 우선순위 큐를 사용하여 풀려고 했는데 시간초과가 났다. stl 사용했는데도 이러는거면 자료구조 사용하는게 아닌가?

2. 알고리즘의 min_element 를 사용하여 풀어보기 -> 아무래도 트리 구조로 만드는게 맞는 거 같긴 한데..

     -> cin.tie 와 ios_base::sync_with_stdio 가 10만개정도면 괜찮을 줄 알았는데 차이가 꽤 많이 나는 것 같다. 꼭 쓸 것

 

[Point]

1. 우선순위 큐 에 대해서 알고 있으면 쉽게 풀린다.

2. 기본이 내림차순 less<T>, 오름차순은 greater<T>