백준 1927 - 최소 힙

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

1927번: 최소 힙

풀이

key 값이 오름차순으로 자동 정렬되는 map을 사용했다. 일반 map의 경우 중복이 제거되므로, 중복이 제거되지 않는 multimap으로 문제를 해결했다.

 

map이 비어있지 않고, 0이 입력되면 map의 맨 처음에 있는 값을 출력한 후, 그 값을 지우고, map이 비어있는데 0이 입력되면 0을 출력한다. 입력값이 0이 아니라면 map에 입력받은 수를 추가한다.

 

코드

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

int main()
{
    ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
    multimap<long,int> m1;

    int n;
    cin>>n;
    for(int i=0; i<n; i++)
    {
        long a;
        cin>>a;
        if(a==0 && !m1.empty()) 
        {
            cout<<m1.begin()->first<<'\n'; 
            m1.erase(m1.begin());
        }
        else if(a==0 && m1.empty()) cout<<"0"<<'\n';
        else m1.insert({a,i});
    }
}