[백준] 1927 최소 힙

 

문제를 읽어보고 오자.

https://www.acmicpc.net/problem/1927

1927번: 최소 힙

 

배열에 값을 넣고, 가장 작은 값 부터 pop연산을 하면 된다. 하지만 문제 조건을 보면 최대 10만개의 값이 들어올 수 있으며, 일반적인 배열로 계산하게 되면은 시간 초과가 나게 될 확률이 높다. 여기서 사용해야 할 자료형은 힙 구조 또는 이진 트리 구조를 사용하는 자료구조를 사용하는 것이다.

 

C++에서는 이러한 구조를 priority_queue 로 구현해 두어서, 사용이 매우 간단하다. 원소를 삽입하는 순간 알아서 정렬이 되게 한다. 지금 다시 힙 또는 이진 트리 구조를 구현하라고 하면, 구현하기 힘들어할 것 같다. 나중에 다시 복습해야겠다.

 

#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int num, temp;
    priority_queue<int, vector<int>, greater<int>> q;
 
    cin >> num;
    while (num--)
    {
        cin >> temp;
        if (!temp)
        {
            if (!q.size())
                cout << "0" << "\n";
            else
            {
                cout << q.top() << "\n";
                q.pop();
            }
        }
        else
            q.push(temp);
    }
    return (0);
}