득이공간

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

PS/알고리즘 문제풀이

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

쟁득 2024. 2. 17. 08:55
 

11286번: 절댓값 힙

첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0

www.acmicpc.net

#include <iostream>
#include <queue>
using namespace std;

template <class _Ty>
struct compare {
    constexpr bool operator()(const _Ty& _Left, const _Ty& _Right)
    {
        return (abs(_Left) == abs(_Right)) ? _Left > _Right : abs(_Left) > abs(_Right);
    }
};

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

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

    int N;
    cin >> N;
    for (int i = 0; i < N; ++i)
    {
        int Input;
        cin >> Input;
        if (Input == 0)
        {
            if (MinHeap.empty())
            {
                cout << 0 << '\n';
            }
            else
            {
                cout << MinHeap.top() << '\n';
                MinHeap.pop();
            }
        }
        else
        {
            MinHeap.emplace(Input);
        }
    }
}

 

priority_queue 컨테이너를 사용해서 주어진 연산을 수행하도록 프로그램을 작성하는 문제입니다.

절대값 기준의 최소값 힙이면서, 절대값이 같은 원소가 여러개일 경우 크기가 작은 수를 top에 위치시키도록 하는 조건이 주어졌습니다.

따라서 해당 조건에 맞게 비교 조건자를 생성해주고 priority_queue 선언에 함수객체 형식으로 넣어주어 풀었습니다.