[백준] 11286번 : 절댓값 힙

---

🔗 문제 링크

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

---

반응형

728x90

👩‍💻 코드

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

struct CustomCompare{
    bool operator()(int a, int b){
        int absA = abs(a);
        int absB = abs(b);
        
        if(absA == absB){
            return a > b;
        }else{
            return absA > absB;
        }
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int N;
    cin >> N;
    
    priority_queue<int, vector<int>, CustomCompare> pq;
    
    for(int i=0; i<N; i++){
        int x;
        cin >> x;
        
        if(x == 0){
            if(pq.empty()){
                cout << "0\n";
            }else{
                cout << pq.top() << "\n";
                pq.pop();
            }
        }else{
            pq.push(x);
        }
    }
    
    return 0;
}

---

📝 풀이

이 문제는 정렬을 정의한 우선 순위 큐를 사용하면 쉽습니다.

절댓값이 작은 수를 우선하고 절댓값이 같다면 작은 수를 우선합니다.

주어진 조건대로 정렬을 정의하였기 때문에 우선 순위 큐의 top은 가장 작은 수입니다.

 

정수 x가 0일 때 큐가 비어있다면 0을 출력하고 그렇지 않으면 우선 순위 큐의 top을 출력 후 제거합니다.

정수 x가 0이 아닐 때 우선 순위 큐에 x를 push 합니다.