[ C++ / 우선순위 큐 ] 백준 11286 - 절대값 힙

Minsu._.Lighting·2023년 11월 10일

🔗 자료구조 / 알고리즘

목록 보기

4/9

📄 문제

절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다.
배열에 정수 x (x ≠ 0)를 넣는다.
배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.
절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.
프로그램은 처음에 비어있는 배열에서 시작하게 된다.

⌨ 입력

첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 정수는 -231보다 크고, 231보다 작다.

💻 출력

입력에서 0이 주어진 회수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 절댓값이 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다.

📌 예제

[ Input ]

18
1
-1
0
0
0
1
1
-1
-1
2
-2
0
0
0
0
0
0
0

[ Output ]

-1
1
0
-1
-1
1
1
-2
2
0

📝 풀이

핵심

절대 값 정렬, 절대 값이 같을 시 음수, 양수에 따른 정렬 총 2가지 조건으로 정렬을 해야 함.

우선순위 큐 이용이 핵심!

📌 우선순위 큐 선언
priority_queue<자료형, Container, 비교 함수> que;
📌 비교 함수 정의
우선순위 큐 정렬 조건을 함수로 정의해 주자!

두 수가 같다면 작은 값을 앞으로
두 수가 다르다면 절대 값이 작은 값을 앞으로

소스 코드

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

struct compare
{
    bool operator()(int iNum1, int iNum2)
    {
        int iFirst = abs(iNum1);
        int iSecond = abs(iNum2);

        if (iFirst == iSecond)
        {
            return iNum1 > iNum2;
        }
        else
        {
            return iFirst > iSecond;
        }
    }
};

int iN = 0;

priority_queue<int, vector<int>, compare> que;

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

    cin >> iN;

    for (int i = 0; i < iN; ++i)
    {
        int iNumber = 0;

        cin >> iNumber;

        if (iNumber == 0)
        {
            if (que.empty())
                cout << "0" << '\n';
            else
            {
                cout << que.top() << '\n';
                que.pop();
            }
        }
        else
        {
            que.emplace(iNumber);

        }
    }

    return 0;
}