Baekjoon 11286번 절댓값 힙

문제

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

걸린 시간

00 : 38 : 49

풀이

C++

#include <bits/stdc++.h>
#define INF 987654321
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    map<int, priority_queue<int, vector<int>, greater<int>>> m;
    while(n--){
        int op;
        cin >> op;
        // 추가 연산
        if(op != 0){
            if(m.find(abs(op)) == m.end()){
                priority_queue<int, vector<int>, greater<int>> pq;
                pq.push(op);
                m.insert(make_pair(abs(op), pq));
            }
            else
                m[abs(op)].push(op);
        }
        // 출력 후 제거 연산
        else{
            if(m.empty())
                cout << 0 << "\n";
            else{
                auto it = m.begin();
                if(it->second.size() > 1){
                    int tmp = it->second.top();
                    it->second.pop();
                    cout << tmp << "\n";
                }
                else{
                    cout << it->second.top() << "\n";
                    m.erase(it->first);
                }
            }
        }
    }
    return 0;
}

map 과 우선순위 큐를 이용하여 구현하였다.