pair형 vector 정렬하기 / vector<pair< a, b>> sort /compare, greater, less

알고리즘 문제를 풀다 보면 언어에 이미 구현되어있는 헤더를 사용하면 편한 것이 많습니다. 

그중 많이 쓰이는 것이 pair와 vector입니다. 
이 두가지를 혼용할 경우, 정렬해야 할 경우가 심심치 않게 많습니다. 

이 방법을 정리해보겠습니다. 

 

 

 

 

 

 

1. greater, less

 

sort(v.begin(), v.end()); // 오름차순
sort(v.begin(), v.end(), less<>()); // 오름차순
sort(v.begin(), v.end(), greater<>()); // 내림차순

 

=> 기본적으로 greater와 less를 지정해주지 않으면 오름차순으로 정렬됩니다. 

 

오름차순 : 양 또는 수가 차례로 늘어가는 것 , 작은 것부터 큰 것으로 가는 순서  내림차순 : 양 또는 수가 차례로 줄어가는 것, 큰 것부터 작은 것으로 가는 순서

 

 

 

 

 

 

 

2. 개발자가 직접 비교함수 제작

 

bool cmp(const pair<int, int> &a, const pair<int, int> &b)
{
   if (a.first == b.first) {
        return a.second < b.second;
    }
    else {
        return a.first < b.first;
    }
}

 

=> 해당하는 방법은 정렬하는 방법을 따로 정의해줘야 하는 경우에 사용할 수 있습니다. 

=> 해당 방법은 백준 11650 좌표 정렬하기에서 사용합니다. 

https://codingham.tistory.com/184

백준 11650 - 좌표 정렬하기

=> 한번 풀어볼만한 문제입니다. 

 

 

 

 

2차원 평면 위의 점 N개가 주어진다. 좌표를 x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오.

=> 이러한 정렬을 하기 위해 작성한 비교 함수입니다. 

 

< : 오름차순 > : 내림차순

 

 

<적용>

 sort(arr.begin(), arr.end(), cmp);

=>이와 같이 적용할 수 있습니다. 

=> 사용할 때의 비교함수는 실제 함수의 원형이 아닌, 함수의 이름을 적어줘야합니다.