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

문제 이해

- 절댓값 힙을 구현하려고 한다.

- 두 가지 연산을 지원한다.

1. 배열에 정수 x (x != 0)를 넣는다.

2. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.

※단, 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.

- 프로그램은 비어있는 배열에서 시작한다.

 

<조건>

- 시간 제한: 1초

- 메모리 제한: 256MB

 

<입력>

N: 연산의 개수 (1 ~ 100,000, 10^5)

x: 연산에 대한 정보

- 만약 0이 아니라면 배열에 x값을 넣는 연산 (정수는 int형 범위 안의 수이다)

- 만약 0이라면 배열에서 절댓값이 가장 작은 값을 배열에서 제거하는 경우

 

<출력>

- 입력에서 0이 주어진 횟수만큼 답을 출력한다.

- 만약 배열이 비어 있는 경우에 0이 입력됐을 경우 0을 출력하라.

 

 

---

문제 풀이

처음에는 양수를 위한 우선순위 큐와 음수를 위한 우선순위 큐 두 개를 선언하여

구현하였다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
#define INF 987654321

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

    priority_queue <int, vector<int>, greater<int>> pqPlus;
    priority_queue <int> pqMinus;

    int n;
    cin>>n;
    while(n--){
        int x;
        cin>>x;

        if(x > 0){
            pqPlus.push(x);
        }else if(x < 0){
            pqMinus.push(x);
        }else{
            if(pqPlus.empty() && pqMinus.empty()){
                cout<<"0\n";
            }else if(pqPlus.empty() && !pqMinus.empty()){
                cout<<pqMinus.top()<<"\n";
                pqMinus.pop();
            }else if(!pqPlus.empty() && pqMinus.empty()){
                cout<<pqPlus.top()<<"\n";
                pqPlus.pop();
            }else{
                if(pqPlus.top() >= abs(pqMinus.top())){
                    cout<<pqMinus.top()<<"\n";
                    pqMinus.pop();
                }else{
                    cout<<pqPlus.top()<<"\n";
                    pqPlus.pop();
                }
            }
        }
    }

    return 0;
}

 

성공적으로 AC를 받았으나 더 좋은 풀이를 찾아낼 수 있었다!

 

 

바로 우선순위 큐에 구조체를 이용하는 방법이다.

struct cmp{
    bool operator()(int a, int b){
        if(abs(a) == abs(b)) return a > b;
        return abs(a) > abs(b);
    }
};

위와 같이 구조체를 선언해주면 훨씬 간결한 코드로 구현할 수 있다.

꼭 배워두도록 하자!

 

 

---

전체 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
#define INF 987654321

struct cmp{
    bool operator()(int a, int b){
        if(abs(a) == abs(b)) return a > b;
        return abs(a) > abs(b);
    }
};

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

    priority_queue <int, vector<int>, cmp> pq; 
    
    int n;
    cin>>n;
    while(n--){
        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;
}

 

 

 

---

배운 점

우선순위 큐에 오름차순, 내림차순말고도 비교 방식을 적용할 수 있다는 걸 배울 수 있었다.

구조체를 선언하는 방법을 꼭 기억하자!