11286 절대값 힙

11286 절대값 힙 (c++)

문제

https://www.acmicpc.net/problem/11286

접근 방식

우선순위 큐 우선순위 큐에 특정 비교 함수를 넣어주면 해결되는 문제

• 순위권에 들기 위해선 직접 MeanHip을 작성해야 한다.

문제 풀이

#include <stdio.h>
#include <queue>
using namespace std;

inline int Abs(int a) { return a < 0 ? -a : a; }
inline int Min(int a, int b) { return a < b ? a : b; }
struct cmp
{
    bool operator()(int a, int b)
    { 
        if (Abs(a) == Abs(b))
            return a > b;
        return Abs(a) > Abs(b);
    }
}; 

int main()
{
    priority_queue<int, vector<int>, cmp> pq;
    int N, num;
    scanf("%d", &N);
    while (N-- > 0)
    {
        scanf("%d", &num);
        if (num == 0)
        {
            if (pq.empty()) printf("0\n");
            else { printf("%d\n", pq.top()); pq.pop(); }
        }
        else
        {
            pq.push(num);
        }
    }

    return 0;
}

다시 생각해볼 점

1. 항상 (최소/최대)값을 출력한다 -> 우선순위 큐