[C++] 백준 알고리즘 11268번 절댓값 힙 - Refactoring

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

11286번: 절댓값 힙

1년 6개월 전(?) 이 문제를 푼 적이 있었다,

예전에는 음수, 양수를 따로 우선순위 큐를 이용해서 작은 수를 기준으로 정렬했는데 (greater<int> 사용)

새로이 풀어보면서 우선순위 큐의 정렬 기준을 직접 변경하는 방법이 있길래 사용해봤다.

구조체와 operator 메소드를 사용하면 된다.

 

(저번에 푼 방식)

https://sxyzn.tistory.com/38

[C++] 백준 알고리즘 11268번 절댓값 힙

 

(새로운 방식)

#include<iostream>
#include<queue>

using namespace std;

struct cmp{
    bool operator()(int a, int b){
        if(abs(a)==abs(b)){
            return a>b; // 절댓값 같으면 음수(더 작은 수)부터
        }
        else return abs(a)>abs(b); // 절댓값 다르면 절댓값 작은 것 부터
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, input;
    cin>>n;
    priority_queue<int, vector<int>, cmp>pq;
    while(n--){
        cin>>input;
        if(input==0){
            if(pq.empty()) cout<<"0"<<'\n';
            else{
                cout<<pq.top()<<'\n';
                pq.pop();
            }
        }
        else{
            pq.push(input);
        }
    }
}

잘 보면 sort 함수를 사용할 때 cmp를 사용해 정렬 기준을 직접 변경하는 것이랑 비슷하다.

 

struct cmp{
    bool operator()(int a, int b){
        if(abs(a)==abs(b)){
            return a>b; // 절댓값 같으면 음수(더 작은 수)부터
        }
        else return abs(a)>abs(b); // 절댓값 다르면 절댓값 작은 것 부터
    }
};

이 부분을 통해 정렬을 재정의 할 수 있다,

if 문 안에 return을 a>b로 하면 절댓값이 같은 경우, 더 작은 수의 우선순위를 높게 한다. (2와 -2가 있으면 -2 우선)

else 문 안에 return 을 abs(a)>abs(b) 로 하면, 절댓값이 다를 경우, 더 작은 수의 우선순위를 높게 한다. (1과 -2가 있을 때 -2을 우선)

 

위에서 정의한 정렬 기준은, 아래와 같이 우선순위 큐와 함께 사용한다.

priority_queue<int, vector<int>, cmp> pq;