✅ 우선순위 큐 (힙)

문제

링크

풀이

방법1

• 우선순위 큐를 두개 사용한다.
• 음수는 음수 전용 최대힙 우선순위 큐에 넣는다. (편하게 절댓값 비교를 위해)
• 양수는 양수 전용 최소힙 우선순위 큐에 넣는다.
• 각각에서 두개의 최상위 값을 꺼내 절댓값이 작은 값을 우선 출력하고 절댓값이 같은 경우에는 작은 수를 출력하므로 음수 우선으로 출력한다.
• 둘중 하나의 큐가 먼저 다 비어졌을 경우도 고려한다.

방법2

• 절댓값을 작은 순으로 출력해야 하므로 절댓값을 최소힙 우선순위 큐에 넣는다.
• 대신 절댓값이 같은 경우 원래값이 더 작은 경우를 출력해야 하므로 pair<절댓값, 원래값> 으로 큐에 넣는다. 이과정에서 최소힙이므로 절댓값이 같은 경우 자동으로 다음 값인 원래값으로 크기를 비교해서 넣어진다.

방법 1, 2 둘 다 가능하지만 방법1은 자동으로 해주는 방법2와 달리 손수 분기를 만들어 값을 비교하는 과정이 필요하므로 좀 더 복잡하다. 방법2로 결정!

코드

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

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    cin >> N;

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> que;

    for(int i=0;i<N;i++){
        int num;
        cin >> num;

        if(num != 0){
            que.push(make_pair(abs(num), num));
        }
        else{
            if(que.empty()) cout << "0" << "\n";
            else{
                cout << que.top().second << "\n";
                que.pop();
            }
        }
    }

    return 0;
}