[C++] 우선순위큐 구조체 사용하는 법, 알고리즘, 이론

알고리즘 문제를 풀다보면, 우선순위큐를 사용할 일이 많다. 우선순위큐의 장점은 원하는 구조체를 선언하고 원하는대로 정렬 방식을 정할 수 있다는 것이다.

 

 

 

 

typedef struct item {

    string pre;

    int number;

    int idx;

    item(string p, int n, int i) : pre(p), number(n), idx(i) {};

}item;

 

struct cmp {

    bool operator()(item i1, item i2) {

        if (i1.pre.compare(i2.pre) == 0) {

            if (i1.number == i2.number) 

                return i1.idx > i2.idx;

            else

                return i1.number > i2.number;

        }

        else

            return i1.pre.compare(i2.pre) > 0;

    }

};

 

 

 

 

위 예제는, 알고리즘 문제를 풀다가 작성한 코드이다. 여기서, 코드를 이해할 필요는 없고, 다양한 변수들을 대소 관계로 정렬할 수 있다는 게 핵심이다.

 

 

 priority_queue<item, vector<item>, cmp> p_q

 

 

위의 형태로 변수를 선언하고, push 연산을 사용하면, cmp에서 정의한 방식대로 값이 정렬된다.

 

 

 

우선순위큐를 자주 사용하지 않은 사람들은 cmp 구조체를 선언하는데 익숙하지 않을 것이며, 또한 동작도 다르게 한다.

 

 

 

 

struct cmp {

    bool operator()(item i1, item i2) {

....

 

 

 

 

위의 함수는 return 값이 true일 경우 i1과 i2를 그대로 두고, false일 경우 i1과 i2를 swap한다.

 

 

 

 

여기서 주목해야할 것은, i2가 먼저 pop되는 아이템이라는 것이다.

 

 

 

 

헷갈릴 수 있는 것은 vector같은 자료구조로 sort를 할 때와는 반대이다. vector는 앞에서 부터 값을 참조하고 priority_queue는 뒤에서 부터 값을 참조하므로 비교 함수가 반대로 작성되는 것이다.

 

 

 

 

이 부분을 기억하면, cmp 구조체를 착각해서 작성할 일은 없을 것이다.