[백준][C++] 11286번: 절대값 힙 <224>

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

 

11286번: 절댓값 힙

생각의 흐름

문제 자체는 엄청 쉽다. 그냥 Queue 2개 만들어서 각각 minus, plus 용으로 사용하면 된다.

 

다만 주의할점이... 아무 생각없이 그냥 queue를 사용하면서 삽질하면 안된다.

우선순위큐를 사용해서 minHeap을 만들어줘야 한다.

priority_queue<int, vector<int>, greater<int>> plusQ;
priority_queue<int, vector<int>, greater<int>> minusQ;

 

나의 코드

#include <bits/stdc++.h>
#include <iostream>
using namespace std;

int T;
priority_queue<int, vector<int>, greater<int>> plusQ;
priority_queue<int, vector<int>, greater<int>> minusQ;

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

    cin >> T;
    while (T--) {
        int num;
        cin >> num;

        if (num == 0) {
            if(plusQ.size() == 0 && minusQ.size() == 0) {
                cout << 0 << "\n";
                continue;
            }else if(plusQ.size() == 0){
                cout << minusQ.top() * -1 << "\n";
                minusQ.pop();
                continue;
            }else if(minusQ.size() == 0) {
                cout << plusQ.top() << "\n";
                plusQ.pop();
                continue;
            }

            int plusFront = plusQ.top();
            int minusFront = minusQ.top();

            if(plusFront > minusFront) {
                cout << minusFront * -1 << "\n";
                minusQ.pop();
            }else if(plusFront < minusFront){
                cout << plusFront << "\n";
                plusQ.pop();
            }else {
                cout << minusFront * -1 << "\n";
                minusQ.pop();
            }
        } else {
            if (num > 0) {
                plusQ.push(num);
            } else {
                minusQ.push(abs(num));
            }
        }
    }

    return 0;
}