[Algorithm] priority_queue 비교연산자 구현 (feat. struct compare, 외우기 쉬운 방법)

알고리즘 문제를 풀다보면 priority_queue에 int형이 아닌 pair를 이용하고 struct를 이용할 때가 있어서 내가 원하는 순서대로 priority_queue를 출력하려면 비교연산자를 재정의 해주어야한다. 오늘은 어떻게 priority_queue의 비교연산자를 구현하는지 알아보도록 하자.

---

c++에서 sort 함수를 사용할 때, 사용자가 원하는 순서대로 정렬하고 싶으면 cmp 함수를 따로 만들어서 사용하였다. 

#include <algorithm>
#include <stdio.h>

bool cmp(int a, int b)
{
	return a < b;
}
int main()
{
	vector <int> v;
    v.push_back(1);
    v.push_back(3);
    v.push_back(2);
	sort(v.begin(),v.end(),cmp);
}

 

sort와 다르게 priority_queue에서는 구조체를 만들어서 자신이 원하는 순서대로 정렬시킬 수 있다. (struct cmp를 만들고 operator() 를 오버로딩한다)

 

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

struct jewelry
{
    int weight;
    int price;
};

vector<struct jewelry> jewelry;

//priority_queue를 비교연산자 재정의
struct cmp 
{
    bool operator()(struct jewelry a, struct jewelry b)
    {
        if(a.price == b.price)
        {
            return a.weight < b.weight;
        }
        else return a.price > b.price;
    }
};

int main()
{
   
    priority_queue<struct jewelry, vector<struct jewelry>, cmp> pq;
    //cmp를 마지막에 추가해주면서 자신이 원하는 순서대로 정렬시킴.
    
    struct jewelry j1;
    j1.weight = 10;
    j1.price = 100;
    pq.push(j1);
    
    struct jewelry j2;
    j2.weight = 20;
    j2.price = 200;
    pq.push(j2);
    
    struct jewelry j3;
    j3.weight = 30;
    j3.price = 300;
    pq.push(j3);
    
    struct jewelry j4;
    j4.weight = 40;
    j4.price = 400;
    pq.push(j4);
    
    struct jewelry j5;
    j5.weight = 11;
    j5.price = 100;
    pq.push(j5);
    
    while(!pq.empty())
    {
        int w = pq.top().weight;
        int p = pq.top().price;
        pq.pop();
        printf("%d %d\n", p, w);
    }
    
}

결과는 다음과 같이 출력이 된다.

 

---

쉽게 외우는방법

쉽게 외우는 방법을 다음과 같이 정리 할 수 있다.