[C++] 우선순위 큐(PRIORITY_QUEUE) & 페어(PAIR) 사용법

개요

우선순위 큐는 컨테이너 안의 자료들을 내림차순 혹은 오름차순으로 정렬해주는 자료형이다.

 

그런데 pair와 같이 자료가 두 개 이상이 되면 어떻게 될까??

 

 

간략하게 알아보도록 하자.

 

 

1. 기본 사용법(내림차순)

첫 번째 인자를 기준으로 내림차순으로 정렬된다.

첫 번째 인자가 같다면 두 번째 인자를 기준으로 내림차순 정렬된다.

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

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

    priority_queue<pair<int, int>> pq;

    pq.push({1, 1});
    pq.push({1, 2});
    pq.push({2, 3});
    pq.push({5, 1});
    pq.push({3, 5});

    int size = pq.size();
    for(int i = 0; i < size; i++){
        cout<<pq.top().first<<" "<<pq.top().second<<"\n";
        pq.pop();
    }
   
    return 0;
}

 

<출력>

5 1
3 5
2 3
1 2
1 1

 

 

 

2. 오름차순 정렬법

greater<>를 우선순위 큐 선언할 때 사용해준다.

 

첫 번째 인자 기준으로 오름차순 정렬한 뒤,

첫 번째 인자가 같다면 두 번째 인자 기준으로 오름차순 정렬한다.

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

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

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int ,int>>> pq;

    pq.push({1, 1});
    pq.push({1, 2});
    pq.push({2, 3});
    pq.push({5, 1});
    pq.push({3, 5});

    int size = pq.size();
    for(int i = 0; i < size; i++){
        cout<<pq.top().first<<" "<<pq.top().second<<"\n";
        pq.pop();
    }
   
    return 0;
}

 

 

<출력>

1 1
1 2
2 3
3 5
5 1

 

 

 

사용자 정의 정렬방법

cmp 구조체를 따로 선언하여 만든다음,

우선순위 큐를 선언할 때 넣어주면 원하는대로 정렬할 수 있다.

 

아래의 코드는

첫 번째 인자는 내림차순

두 번재 인자는 오름차순으로 정렬하도록 만든 코드이다.

 

우선순위 큐의 경우 가장 위의 있는 것을 빼오는 것이니

오름차순과 내림차순을 헷갈리지 않도록 하자.

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

struct cmp{
    bool operator()(pair<int, int>&a, pair<int, int>&b) {
        if (a.first == b.first) {
            return a.second > b.second;
        }return a.first < b.first;
    }
};

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

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

    pq.push({1, 1});
    pq.push({1, 2});
    pq.push({2, 3});
    pq.push({5, 1});
    pq.push({3, 5});

    int size = pq.size();
    for(int i = 0; i < size; i++){
        cout<<pq.top().first<<" "<<pq.top().second<<"\n";
        pq.pop();
    }
   
    return 0;
}

 

<출력>

5 1
3 5
2 3
1 1
1 2