[백준] 11286번 절댓값 힙 (Python,C++)

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

11286번: 절댓값 힙

 

해당문제는 파이썬의 경우 튜플과 최소힙/최대힙을 따로 두는 형식으로 풀 수있었으며 C++은 후자의 방식으로 풀었다. 

파이썬 튜플의 경우 정렬시 맨앞의 값을 기준으로정렬해나가며,값이같다면 뒤의 값으로 정렬을 이어나간다.

 

헷갈리지말자.파이썬은 최소힙이 기본이며,C++은 최대힙을 기본으로 지원한다!

 

---

SOLUTION CODE

# PYTHON

1) 튜플 이용

import heapq as hq
import sys

input = sys.stdin.readline
pq = []

for _ in range(int(input())):
    x = int(input())
    if x:
        hq.heappush(pq, (abs(x), x))
    else:  # 0인경우 출력
        print(hq.heappop(pq)[1] if pq else 0)

2) min_heap,max_heap따로 구현

import heapq as hq
import sys

input = sys.stdin.readline
min_heap = []  # 1, 2, 3, 8, 13, 99, 242 양수(제일작은값=절댓값 제일작은값)
max_heap = []  # -1, -4, -10, -1042 음수(제일큰값=절댓값 제일작은값)

for _ in range(int(input())):
    x = int(input())
    if x:
        if x > 0:
            hq.heappush(min_heap, x)
        else:
            hq.heappush(max_heap, -x)  # 최대힙으로 작동

    else:
        if min_heap:
            if max_heap:
                if min_heap[0] < abs(-max_heap[0]):  # max_heap[0]
                    print(hq.heqpopop(min_heap))
                #                elif min_heap[0] > abs(max_heap[0]):
                #                    print(hq.heqpopop(max_heap))
                else:
                    print(-hq.heqpopop(max_heap))

            else:
                print(hq.heappop(min_heap))

        else:  # min_heap 빈 경우
            if max_heap:
                print(-hq.heappop(max_heap))
            else:
                print(0)  # 둘다 빈경우
            pass

---

# C++

1) min_heap,max_heap따로 구현

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

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N;
    int x;
    priority_queue<int, vector<int>, greater<int>> min_heap; // 최소힙 오름차순
    priority_queue<int> max_heap;                            // 최대힙(기본) 음수내림차순

    cin >> N;
    for (int i = 0; i < N; i++)
    {
        cin >> x;
        if (x)
        {
            if (x > 0)
            {
                min_heap.push(x);
            }
            else
            {
                max_heap.push(x);
            }
        }
        else
        { // x가 0일때 출력
            if (min_heap.empty())
            { // 양수힙비었을때-----------------
                if (max_heap.empty())
                {
                    cout << "0\n"; // 음수힙 비었을때(둘다비었을때)
                }
                else
                {
                    cout << max_heap.top() << '\n';
                    max_heap.pop();
                }
            }
            else
            { // 양수힙 안비었을때-----------------
                if (max_heap.empty())
                { // 음수힙 비었을때
                    cout << min_heap.top() << '\n';
                    min_heap.pop();
                }
                else
                { // 음수힙 안비었을때 (둘다안비었을때)
                    if (-max_heap.top() > min_heap.top()) //절댓값비교 -5,1
                    {
                        cout << min_heap.top() << '\n';
                        min_heap.pop();
                    }
                    else
                    {
                        cout << max_heap.top() << '\n';
                        max_heap.pop();
                    }
                }
            }
        }
    }
}

2) cmp에서 정렬 구현

#include <iostream>
#include <queue>
#include <vector>
#include <cmath>

using namespace std;

struct cmp
{ // 정렬 기준 함수
    bool operator()(int a, int b)
    {
        if (abs(a) == abs(b))
        {                 // 절댓값이 같다면 -1,1
            return a > b; // 오름차순(-1,1)
        }
        // 절댓값이 다르다면 4,-6
        return abs(a) > abs(b); // 절댓값기준 오름차순(4,-6)
    }
};

int main()
{
    int N, x;
    priority_queue<int, vector<int>, cmp> q;
    cin >> N;

    for (int i = 0; i < N; i++)
    {
        cin >> x;
        if (x == 0)
        { // 0일때 출력
            if (q.empty())
            {
                cout << "0\n";
            }
            else
            {
                cout << q.top() << '\n';
                q.pop();
            }
        }
        else
        { // 0이 아닐때 값 넣기
            q.push(x);
        }
    }
    return 0;
}