[Baekjoon] 11286: 절댓값 힙 - (C3, S1) Min Heap

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

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

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

11286번: 절댓값 힙

 

데이터를 <값, 절댓값> 쌍으로 지정하고, 정렬 기준이 절댓값이 작은 것, 값이 작은 것 우선으로 하는 Min Heap을 작성하면 되는 S1 치고는 쉬운 문제이다. 

 

// 람다식 정의
    auto cmp = [](const pair<int, int> &a, const pair<int, int> &b)
    {
        if (a.second > b.second) // second 값을 기준으로 min-heap
            return true; 
        if (a.second == b.second) // second가 같으면 first 기준
            return a.first > b.first;
        return false; // 나머지
    };

    // pair의 first가 입력값, second가 절대값
    priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> min_heap(cmp);

priority_queue를 pair<int, int>를 대상으로 사용자 정의 정렬 기준을 작성하기 위해 람다식을 작성한다. decltype은 C++11에서 도입된 키워드로, 표현식의 타입을 컴파일러가 추론하여 반환한다. priority_queue의 세 번째 매개변수는 비교자의 타입을 명시해야 한다. 그런데, 람다식은 익명 함수 객체로, 명시적인 타입 이름이 없다. 따라서 람다식의 타입을 추론하려면 decltype을 사용해야 한다.

 

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

int main()
{
    // freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    // 람다식 정의
    auto cmp = [](const pair<int, int> &a, const pair<int, int> &b)
    {
        if (a.second > b.second) // second 값을 기준으로 min-heap
            return true; 
        if (a.second == b.second) // second가 같으면 first 기준
            return a.first > b.first;
        return false; // 나머지
    };

    // pair의 first가 입력값, second가 절대값
    priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> min_heap(cmp);

    while (N--)
    {
        int input;
        cin >> input;

        if (input == 0)
            if (min_heap.empty())
                cout << 0 << '\n';
            else
            {
                cout << min_heap.top().first << '\n';
                min_heap.pop();
            }

        else
            min_heap.push({input, abs(input)});
    }
}