[Algorithm] Sort() & compare 함수 :: C++

오늘 백준에서 문제를 풀다가 vector정렬 시 내가 원하는 순서대로 커스텀해서 정렬하는 compare함수를 만들어서 사용하다가 Runtime Error를 만나서 구글링으로 알아낸 결과를 정리하려고 한다. 결론은 벡터를 정렬하기 위해 sort로 넘겨준 cmp 함수가 잘못돼서 발생한 문제였다.

1. C++ 공식 문서에서 알아보는 Sort

C++ STL의 sort함수는 수학적으로 strict weak ordering 조건을 만족해야 한다. 

1. cmp(a, a) == false 

2. cmp(a, b) == true이면 cmp(b, a) == false. 두 비교체를 바꾸면 참/거짓 값도 변경되어야한다.

3. cmp(a, b) == true이고 cmp(b, c) == true이면 cmp(a, c) == true이다.

https://en.cppreference.com/w/cpp/named_req/Compare

C++ named requirements: Compare - cppreference.com

2. 내가 짠 코드는? - Boj30970-선택의 기로

여기서 나는 pair로 받았다. 테스트 케이스에서 품질과 가격이 같은 케이스가 여러번 나올수도 있다.

문제가 발생하는 테스트 케이스를 확인해보면

,A:{2, 2}, B:{3, 3}을 cmp1으로 비교할 때

cmp(a, b) == true이면 cmp(b, a) == false 이 조건을 보면

A.first 2 < B.first 3이기 때문에 첫번째 if문에서 false가 나온다.

반대로 A:{3, 3}, B:{2, 2} 로 놓고 다시 보면

3 < 2 는 false가 나온다.

즉 두 비교체를 바꿔도 값이 똑같아서 나는 문제였다.

#include<bits/stdc++.h>

using namespace std;

vector<pair<int, int>> input;

bool cmp1(pair<int, int> &a, pair<int, int> &b) {
    if(a.first < b.first) return false;
    return a.second < b.second;
}

bool cmp2(pair<int, int> &a, pair<int, int> &b) {
    if(a.second < b.second) return true;
    return a.first > b.first;
}

int main() {
    ios_base::sync_with_stdio(false); cout.tie(0); cin.tie(0);
    
    int n;
    cin >> n;
    
    for(int i = 0; i < n; i++) {
        int quality, cost;
        cin >> quality >> cost;
        
        input.push_back({quality, cost});
    }
    
    sort(input.begin(), input.end(), cmp1);
    cout << input[0].first << ' ' << input[0].second << ' ';
    cout << input[1].first << ' ' << input[1].second << '\n';
    
    sort(input.begin(), input.end(), cmp2);
    cout << input[0].first << ' ' << input[0].second << ' ';
    cout << input[1].first << ' ' << input[1].second << '\n';
}

3. 코드 템플릿

아래의 코드 양식을 default 템플릿으로 잡으면 틀일 일이 없을 것 같다.

bool compare(object a, object b) {
    if (a.first != b.first) // 가장 먼저 따져야 할 할 조건
        return a.first > b.first; // 부등호 방향은 문제에 따라 < 또는 > 둘 중 하나를 사용
    if (a.second != b.second) // 두 번째로 따져야 할 조건
        return a.second < b.second; // 부등호 방향은 문제에 따라 < 또는 > 둘 중 하나를 사용
    // ...... 같은 방식으로 if return 문을 작성한다 ......
    return a.final > b.final; // 가장 마지막으로 따져야 할 조건. if 문 없이 < 또는 > 를 사용한 결과를 바로 return.
}

 

 

 

 

 

백준은 아주 최고다 최고!

ref -  https://www.acmicpc.net/board/view/43219

 

글 읽기 - 1181 단어정렬 런타임에러 질문점요