priority_queue, sort에서의 정렬 방법
차이점
1.
- #include < algorithm > : sort에서는 greater가 내림차순
- #include < queue > : priority_queue의 sort에서는 greater가 오름차순
2.
- #include < algorithm > : sort에서는 cmp 함수를 만들 때, 인자의 왼쪽이 기준
- #include < queue > : priority_queue의 sort에서는 cmp 함수를 만들 때, 인자의 오른쪽이 기준
greater 사용하여 정렬
priority_queue
- priority_queue<pair<int, int>, vector<pair<int, int>>, less<pair<int, int>>> pq;
- priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
sort 함수
- sort(v.begin(), v.end()); // 오름차순
- sort(v.begin(), v.end(), greater()); // 내림차순
cmp 사용하여 정렬
1. first 큰 값부터 리턴, first 값이 같다면 second 값이 큰 값부터 리턴
priority_queue
- 기본적으로 priority queue 작동 자체가 first 값이 큰 값부터 리턴, 같다면 second 값이 큰 값부터 리턴이 된다.
bool cmp (pair<int, int> &a, pair<int, int> &b) {
if (a.first == b.first) return a.second < b.second; // pq는 오른쪽이 기준이기 때문에 second 내림차순 정렬
else return a.first < b.first; // first 내림차순 정렬
}sort 함수
bool cmp (pair<int, int> &a, pair<int, int> &b) {
if (a.first == b.first) return a.second > b.second; // sort는 왼쪽이 기준이기 때문에 first 내림차순 정렬
else return a.first > b.first; // sort는 왼쪽이 기준이기 때문에 first 내림차순 정렬
}2. first 큰 값부터 리턴, first 값이 같다면 second 값이 작은 값부터 리턴
priority_queue
bool cmp (pair<int, int> &a, pair<int, int> &b) {
if (a.first == b.first) return a.second > b.second; // second값 기준 오름차순
else return a.first < b.first; // first값 기준 내림차순 (큰 값 우선)
}sort 함수
bool cmp (pair<int, int> &a, pair<int, int> &b) {
if (a.first == b.first) return a.second < b.second;
// sort는 왼쪽이 기준이기 때문에 second 오름차순 정렬
else return a.first > b.first;
// sort는 왼쪽이 기준이기 때문에 first 내림차순 정렬
}3. first 작은 값부터 리턴, first 값이 같다면 second 값이 작은 값부터 리턴
priority_queue
bool cmp (pair<int, int> &a, pair<int, int> &b) {
if (a.first == b.first) return a.second > b.second; // second값 기준 오름차순
else return a.first > b.first; // first값 기준 오름차순
}sort 함수
bool cmp (pair<int, int> &a, pair<int, int> &b) {
if (a.first == b.first) return a.second < b.second;
// sort는 왼쪽이 기준이기 때문에 second 오름차순 정렬
else return a.first < b.first;
}
