[#11286] 절댓값 힙

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stdio.h>
#include <queue>
 
using namespace std;
 
int main() {
    int n;
    scanf("%d", &n);
 
    priority_queue<int, vector<int>, less<int>> na;  //음수. 최대힙
    priority_queue<int, vector<int>, greater<int>> po;  //양수. 최소힙
 
    for (int i = 0; i < n; i++) {
        int temp;
        scanf("%d", &temp);
 
        if (temp == 0) {
            //pop
            if (na.empty() && po.empty())
                printf("0\n");
            else if (na.empty() && !po.empty()) {
                printf("%d\n", po.top());
                po.pop();
            }
            else if (!na.empty() && po.empty()) {
                printf("%d\n", na.top());
                na.pop();
            }
            else {
                //둘 다 데이터 있음
                if (na.top() * (-1) < po.top()) {
                    printf("%d\n", na.top());
                    na.pop();
                }
                else if (na.top() * (-1) > po.top()) {
                    printf("%d\n", po.top());
                    po.pop();
                }
                else {
                    //절대값이 같으면
                    printf("%d\n", na.top());
                    na.pop();
                }
 
            }
        }
        else {
            //push
            if (temp < 0)  //음수면
                na.push(temp);
            else  //양수면
                po.push(temp);
        }
    }
 
    return 0;
}

 

음수는 최대힙에, 양수는 최소힙에 따로 저장