구조체를 활용한 priority_queue 비교함수

먼저 우선순위 큐는 보통 힙의 구조를 가지는 비선형 자료구조다.

배열로 구성할 경우엔 1. 자료의 낭비 2. 삽입에서 시간을 크게 잡아먹는다. 또한 연결리스트로 구성할 경우에도 삽입 시간이 배열과 같기에 더 낫다.

따라서 logN의 시간으로 삽입과 삭제를 할 수 있는 힙의 구조로 우선순위 큐를 작성할 수 있다

 

그래서 priority_queue에 우선순위를 줘야 하는데 기본적으로 우선순위는 큰 값이 높게 설정되어 있다

따라서 큰 수부터 출력하고 싶으면 우선순위 큐를 선언만하고 사용하면 된다

문제: https://www.acmicpc.net/problem/11279

https://github.com/surinoel/boj/blob/master/11729.cpp

 

하지만 특정한 구조체에서는 각기 다른 경우의 수들이 우선순위를 정할 수 있다

#include <queue>
#include <iostream>
 
using namespace std;
 
struct custom {
    int x, y, value;
    custom(int v) : x(0), y(0), value(v) {}
};
 
struct cmp {
    bool operator()(const custom &u, const custom &v) {
        return u.value > v.value;
    }
};
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
 
    priority_queue<custom, vector<custom>, cmp> pq;
    pq.push(custom(5));
    pq.push(custom(2));
    pq.push(custom(8));
    pq.push(custom(9));
    pq.push(custom(1));
    pq.push(custom(14));
 
    while (!pq.empty()) {
        cout << pq.top().value << '\n';
        pq.pop();
    }
 
    return 0;
}