[백준 실버1] 11286 절대값 힙

 

중요한 조건은 드래그한 저 줄이다.

 

배열에 입출력에 대한 조건이 있다.

1. 입력할 때 0이 아닐 때,

2. 출력할 때 0일 때,

 

하지만 출력에 조건이 있다.

1. 절대값이 가장 작을 것

2. 절대값이 가장 작은 수가 중복될 경우 가장 작은수 출력(= 음수 출력)

 

출력에 대한 조건에 우선 순위에 대한 명확한 기준이 있다.

이는 우선 순위 큐로 구현하기 적합함을 알 수 있다.

 

 

#include <string>
#include <vector>
#include <iostream>
#include <map>
#include <algorithm>
#include <stack>
#include <queue>
#include <cmath>

using namespace std;

struct compare {
    bool operator()(int a, int b) {
        if (abs(a) == abs(b)) {
            return a > b;
        }
        return abs(a) > abs(b);
    }
};

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, x;
    priority_queue<int, vector<int>, compare> q;
    vector<int> v;
    cin >> n;

    while (n-- != 0)
    {
        cin >> x;
        if (x == 0)
        {
            if (q.empty())
            {
                v.push_back(0);
            }
            else
            {
                v.push_back(q.top());
                q.pop();
            }
        }

        else
        {
            q.push(x);
        }
    }

    for (int i = 0; i < v.size(); i++)
    {
        cout << v[i] << endl;
    }

    return 0;
}