[ 백준 11286 ] 절대값 힙 (C++)

백준의 절대값 힙(11286) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

문제에서 제시한 조건대로 절대값 힙을 구현하면 되는 문제이다.

먼저, '힙(Heap)' 자료구조에 대해서 아직 잘 모른다면 아래의 글을 읽고 오도록 하자.

[ 힙(Heap) 자료구조 알아보기(Click) ]

이 문제에서 힙을 구현할 때는, 힙에서 비교하는 부분을 문제에서 제시한 대로 '절대값 힙' 으로 만들어 주어야 한다.

따라서 본인은 또 다른 'Compare' 함수를 만들어서, 이 함수를 통해서 비교하면서 힙을 만들도록 구현해 주었다.

'Compare' 함수에서는 문제에서 말한대로, 절대값이 가장 작은 값을, 그런 값이 여러개일 때는 가장 작은 값이 더 높은

우선순위를 갖도록 비교해주는 내용을 구현하였다.

[ 소스코드 ]

#include<iostream>
#include<cmath>
 
#define MAX 100010
using namespace std;
 
int N, Heap_Idx;
int Heap_Array[MAX];
 
bool Compare(int A, int B)
{
    int dA = abs(A);
    int dB = abs(B);
    if (dA <= dB)
    {
        if (dA == dB)
        {
            if (A < B)
            {
                return true;
            }
            return false;
        }
        return true;
    }
    return false;
}
 
void Swap(int &A, int &B) { int Temp = A; A = B; B = Temp; }
 
void Heap_push(int data)
{
    int Idx = ++Heap_Idx;
    Heap_Array[Idx] = data;
 
    while ((Idx != 1) && Compare(data, Heap_Array[Idx / 2]) == true)
    {
        Swap(Heap_Array[Idx], Heap_Array[Idx / 2]);
        Idx = Idx / 2;
    }
}
 
int Heap_pop()
{
    if (Heap_Idx == 0) return 0;
    int Result = Heap_Array[1];
    Heap_Array[1] = Heap_Array[Heap_Idx--];
    
    int Parent = 1;
    int Child;
    while (1)
    {
        Child = Parent * 2;
        if (Child + 1 <= Heap_Idx && Compare(Heap_Array[Child + 1], Heap_Array[Child]) == true) Child++;
        if (Child > Heap_Idx || Compare(Heap_Array[Parent], Heap_Array[Child]) == true) break;
        Swap(Heap_Array[Parent], Heap_Array[Child]);
        Parent = Child;
    }
 
    return Result;
}
 
void Solution()
{
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        int a; cin >> a;
        if (a == 0) cout << Heap_pop() << endl;
        else Heap_push(a);
    }
}
 
void Solve()
{
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
    
    return 0;
}