[알게 된 것] - c++에서 연산자 '<' 재정의 시 주의점

 

 

 정렬 알고리즘 문제를 풀 때 sort 함수와 priority_queue사용을 위해 구조체의 연산자 오버로딩을 주로 사용하는 편이다. MST와 같이 우선 순위 큐를 사용하는 문제의 경우 edge의 cost가 작은순으로 정렬이 되어 있어야하므로 아래와 같이 선언하여 사용한다.

 

struct Vertex {
    int u;
    int v;
    int cost;
    bool operator<(const & Vertex v) const {
    	return this->cost > v.cost;
    }
};

 

 

 

 

 

 이 구조체를 우선순위 큐에 삽입 시 cost의 오름차순으로 자동 정렬된다. 이와 비슷하게 algorithm 헤더의 sort함수도 오름차순 혹은 내림차순으로 구조체를 정렬할 수 있는데, 문제는 이게 우선순위 큐와 반대이다. 즉 Vertex구조체를 벡터나 배열에 넣고 sort함수로 정렬한다고 하였을 때 cost에 따라 내림차순 정렬된다는 얘기이다.

 

 

 

 

 

 

 이게 왜 이런지 좀 더 정보를 알아보니 우선 순위 큐는 기본적으로 내림차순 정렬되기 때문에 그렇다고 한다. 그래서 위의 Vertex 구조체는 벡터나 배열에서 sort 함수로 정렬 시 내림차순 정렬이 된다는 것이다.

 

 

 

 

 

 

 분명 코드를 맞게 짰는데 계속 답이 틀리다고 나와서 골치가 아팠는데 위와 같은 문제가 있었다. 실제 코테였으면 한 문제를 날려버린 셈인데, 꼭 기억해두었다가 정렬 문제에서 잘 쓰도록 하자.