11286번(우선순위큐 다시풀기)

11286번 - 절대값 힙

나는 이 문제를 우선 순위큐가 아닌 배열을 통해서 풀어보았다.

최대힙, 최소힙과 비슷한 방식이었지만, 비어있는 큐가 0일 때를 생각해줘야 했고, 크다 작다가 아닌

같은 값일 때도 나눠줘야 했기 때문에 조건이 많이 발생하였다.

그리고 pop 할때 for문에서 i 값 증가량을 명시해놓지 않아서 처음에 많이 틀렸다.

pop 에서 마지막 l !=0 && r!=0 부분에서 많이 헷갈렸었다.. 배열로 풀기는 너무 조건문이 많이 생기는 것 같다..

<정답 코드>

#include<iostream>
 
using namespace std;
int N;
int heap[100001];
int last = 0;
void push(int n)
{
    heap[++last] = n;
 
    for (int i = last; i > 1; i /= 2)
    {
        int p = heap[i/2];
        int n = heap[i];
        
        if(abs(n)<abs(p))
        {
            swap(heap[i], heap[i/2]);
        }
        else
        {
            if (abs(n) == abs(p))
            {
                if (n < p)
                {
                    swap(heap[i], heap[i/2]);
                }
                else
                {
                    break;
                }
            }
            else
            {
                break;
            }
        }
    }
 
}
void pop()
{
    printf("%d\n", heap[1]);
 
    if (last == 0)
    {
        return;
    }
 
    swap(heap[last], heap[1]);
    heap[last--] = 0;
 
    for (int i = 1; i * 2 <= last;)
    {
        int p = heap[i];
        int l = heap[i * 2];
        int r = heap[i * 2 + 1];
 
        if (abs(p) < abs(l) && abs(p) < abs(r))
        {
            break;
        }
        else
        {
            if (l == 0 && r == 0)
            {
                break;
            }
            else if (l == 0 && r != 0)
            {
                if (abs(r) < abs(p))
                {
                    swap(heap[i*2+1], heap[i]);
                    i = i * 2 + 1;
                }
                else 
                {
                    if (abs(r) == abs(p))
                    {
                        if (r < p)
                        {
                            swap(heap[i*2+1], heap[i]);
                            i = i * 2 + 1;
                        }
                        else
                        {
                            break;
                        }
                    }
                    else
                    {
                        break;
                    }
                }
 
            }
            else if (l != 0 && r == 0)
            {
                if (abs(l) < abs(p))
                {
                    swap(heap[i*2], heap[i]);
                    i = i * 2;
                }
                else
                {
                    if (abs(l) == abs(p))
                    {
                        if (l < p)
                        {
                            swap(heap[i*2], heap[i]);
                            i = i * 2;
                        }
                        else
                        {
                            break;
                        }
                    }
                    else
                    {
                        break;
                    }
                }
            }
            else if (l != 0 && r != 0)
            {
                if (abs(l) < abs(r))
                {
                    if (abs(l) < abs(p))
                    {
                        swap(heap[i*2], heap[i]);
                        i = i * 2;
                    }
                    else
                    {
                        if (abs(l) == abs(p))
                        {
                            if (l < p)
                            {
                                swap(heap[i*2], heap[i]);
                                i = i * 2;
                            }
                            else
                            {
                                break;
                            }
                        }
                        else
                        {
                            break;
                        }
                    }
                }
                else if(abs(l)>abs(r))
                {
                    if (abs(r) < abs(p))
                    {
                        swap(heap[i*2+1], heap[i]);
                        i = i * 2 + 1;
                    }
                    else
                    {
                        if (abs(r) == abs(p))
                        {
                            if (r < p)
                            {
                                swap(heap[i*2+1], heap[i]);
                                i = i * 2 + 1;
                            }
                            else
                            {
                                break;
                            }
                        }
                        else
                        {
                            break;
                        }
                    }
                }
                else
                {
                    if (l < r)
                    {
                        if (abs(l) < abs(p))
                        {
                            swap(heap[i], heap[i * 2]);
                            i = i * 2;
                        }
                        else
                        {
                            if (abs(l) == abs(p))
                            {
                                if (l < p)
                                {
                                    swap(heap[i], heap[i * 2]);
                                    i = i * 2;
                                }
                                else
                                {
                                    break;
                                }
                            }
                            else
                            {
                                break;
                            }
                        }
                    }
                    else
                    {
                        if (abs(r) < abs(p))
                        {
                            swap(heap[i], heap[i * 2+1]);
                            i = i * 2+1;
                        }
                        else
                        {
                            if (abs(r) == abs(p))
                            {
                                if (r < p)
                                {
                                    swap(heap[i], heap[i * 2+1]);
                                    i = i * 2+1;
                                }
                                else
                                {
                                    break;
                                }
                            }
                            else
                            {
                                break;
                            }
                        }
                    }
                }
            }
        }
    }
 
 
}
int main()
{
    cin >> N;
    while (N--)
    {
        int op;
        cin >> op;
 
        if (op == 0)
        {
            pop();
        }
        else
        {
            push(op);
        }
    }
 
    return 0;
}