백준 11286 절대값 힙 C++

- 문제

문제 보러가기

priority_queue<pair<int, int>>와 같은 자료구조의 우선순위 큐를 이용하여 풀 수 있는 문제이다. pair의 첫 번째 인자는 입력의 절대값을 두 번째 인자는 음수인지 양수인지 판단할 수 있는 값을 넣어주고 큐의 정렬을 오름차순으로 하면된다.

- 문제 풀이

• priority_queue<pair<int, int>> 자료구조를 사용하며 오름차순으로 정렬하기 위한 functional 라이브러리를 사용하여 priority_queue<자료형, 구현체, 비교연산자> 형식에 맞추어 pq를 선언해준다.
• 첫 번째 인자에 입력의 절대값을 두 번째 인자에 부호를 넣어준다. (음수 -> -1, 양수 -> 1)
• 오름차순으로 정렬했으므로 첫 번째 인자 값이 같은 경우 두 번째 인자가 작은 값이 우선순위가 높다. 문제에서 절대값이 같으면 가장 작은 수를 출력해야하므로 음수가 우선순위가 높게 된다. (만약 양수가 우선순위가 높았다면 두 번째 인자값을 반대로 주어야한다.)
• 입력이 0이 들어온 경우 출력해야하므로 0일 때 첫 번째 인자와 두 번째 인자를 곱한 값을 출력하면 원하는 결과를 얻을 수 있다.

- 코드

#include <iostream>
#include <queue>
#include <vector>
#include <functional>

using namespace std;

int main()
{
    int N, num;
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    vector<int> result;
    cin >> N;

    for(int i = 0; i < N; i++){
        cin >> num;
        if(num == 0){
            if(pq.size() == 0){
                result.push_back(0);
            }
            else{
                result.push_back(pq.top().first * pq.top().second);
                pq.pop();
            }
        }
        else if(num < 0){
            pq.push(pair<int, int>(num*-1, -1));
        }
        else {
            pq.push(pair<int, int>(num, 1));
        }
    }

    for(auto v : result){
        cout << v << endl;
    }
    return 0;
}