[c++] 백준 11286 : 절댓값 힙

[c++] 백준 11286 : 절댓값 힙

🥈실버 1

 

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

11286번: 절댓값 힙

---

접근

우선순위 큐를 활용하여 풀이하는 문제입니다.

 

priority_queue : 우선순위가 높은 것 부터 먼저 pop됨, cmp(나중에 출력하고 싶은 것, 먼저 출력하고 싶은 것) = true가 되게 하면 됩니다.

 

임의로 만든 비교함수를 활용할 경우, 두 요소의 비교에 대한 return 값이 true가 되면 두 값의 순서가 swap이 되고, false가 되면 순서를 그대로 둔다는 것을 인지하고 코드를 작성해야 합니다.

 

문제는 절댓값이 가장 작은 값을 출력하도록 해야하며, 그 값이 여러개일 경우에는 가장 작은 수를 출력하도록 조건을 걸고 있습니다. 예를들어 1, -1 과 같은 값이 입력으로 들어오는 경우 -1, 1 순서대로 출력하라는 것입니다.

 

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

위와 같은 방법으로 우선순위 큐를 선언한 다음, cmp함수를 문제의 조건에 맞게 설정해야 합니다.

두 변수의 절댓값이 같은 경우 앞의 값은 양수이고 뒤의 값이 음수가 오도록 해야하며,

절댓값이 다른 경우 앞의 값이 절댓값이 더 커야하고 뒤의 값이 절댓값이 더 작도록 설정해야 합니다.

 

코드

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

class cmp {
    public:
        bool operator() (int a, int b) {
            if (abs(a) != abs(b)) return abs(a) > abs(b);
            return a > 0 && b < 0;
        }
};

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    priority_queue<int, vector<int>, cmp> Q;
    int N;
    cin >> N;
    while(N--) {
        int val;
        cin >> val;
        if (val == 0) {
            if (Q.empty()) {
                cout << 0 << '\n';
            }
            else {
                cout << Q.top() << '\n';
                Q.pop();
            }
            
        }
        else {
            Q.push(val);
        }
    }
    return 0;
}

cmp가 일반 함수가 아닌 클래스로 정의된 이유는 우선순위 큐 템플릿이 세 번째 인수로 type을 요구하고 있기 때문입니다.

따라서 함수가 아닌 클래스로 선언하여야 인스턴스화 된 cmp가 세번째 인수로 들어갈 수 있게 됩니다.

클래스로 정의하게 되면 비교 논리와 클래스 내 비교에 필요한 추가 상태를 캡슐화할 수 있습니다.

 

operator() 함수는 오버로드된 클래스로서, 우선순위 큐 템플릿이 각 요소들을 비교하는데 사용하는 함수입니다.

임의로 만든 비교함수를 활용할 경우, 이 operator() 함수 내에서 두 요소의 비교에 대한 return 값이 true가 되면 두 값의 순서가 swap이 되고, false가 되면 순서를 그대로 둔다는 것을 인지하고 코드를 작성해야 합니다.