C++ 정렬시 오름차순, 내림차순

백준이나 알고리즘 문제들을 풀다 보면

정렬을 사용하는 문제들은 너무나도 흔하다.

 

그런데, 간혹 이 정렬을 기본으로 세팅된 오름차순이 아닌 내림차순으로 사용해야 하는 경우들이 생긴다.

그 경우들에 대해 알아보자

 

정렬(sort)

기본

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {

    vector<int> v = {3, 2, 0, 9, 7, 1, 4, 8, 6};
    sort(v.begin(), v.end());
    for (int n : v) {
        cout << n << ' ';
    }
    cout << '\n';
    return 0;
}

// 0 1 2 3 4 6 7 8 9

기본적으로 sort는 오름차순으로 구현되어있다.

오름차순

기본적으로 오름차순으로 정렬되어있지만, 명시해주기 위해서는 less<int>를 이용한다

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {

    vector<int> v = {3, 2, 0, 9, 7, 1, 4, 8, 6};
    sort(v.begin(), v.end(), less<int>());
    for (int n : v) {
        cout << n << ' ';
    }
    cout << '\n';
    return 0;
}

// 0 1 2 3 4 6 7 8 9

 

내림차순

내림차순의 경우에는 greater<int>를 이용한다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {

    vector<int> v = {3, 2, 0, 9, 7, 1, 4, 8, 6};
    sort(v.begin(), v.end(), greater<int>());
    for (int n : v) {
        cout << n << ' ';
    }
    cout << '\n';
    return 0;
}

// 9 8 7 6 4 3 2 1 0

 

우선순위 큐(Priority_queue)

#include<queue>
//c++에서 pq는 보통 이렇게 쓰인다. 구현체와 비교연산자는 선택사항
priority_queue<자료형, 구현체, 비교연산자> pq;

알고리즘을 풀다보면, 순차적으로 데이터가 들어오고, 들어오는 동시에 우선순위에 따라 정렬을 해야하는 경우가 생긴다.

그때 이용하는것이 이진트리 기반의 힙으로 구성된 우선순위 큐이다.

 

그러나, 우선순위큐를 이용하다 보면 C++에서는 기본적으로 MaxHeap으로 구성되어있기 때문에, 내림차순으로 구성된 우선순위큐만을 사용할 수 있다.

대부분 편의를 위해 음수부호를 붙여 MaxHeap을 MinHeap으로 전환하긴 하지만, 문제에 따라 int형 범위(- 2^31 ~ 2^31)로 인풋이 주어지는 경우에는, 이 음수 부호를 붙여 MinHeap을 구성하면 오버플로우가 발생해 불가능해진다.

이 부분을 미연에 방지하기 위해 less<int>와 greater<int>를 이용하자.

기본

Max_heap(내림차순)

#include <queue>
#include <iostream>
using namespace std;

int main() {
//기본적으로 pq는 mayheap이다
  priority_queue <int> pq;
  
  pq.push(5);
  pq.push(3);
  pq.push(6);
  pq.push(7);

  while(!pq.empty()) {
    int temp = pq.top();
    cout << temp;
    pq.pop();
  }
  // 출력결과
  // 7653
  return 0;
}

내림차순

less<int>

#include <queue>
#include <iostream>
using namespace std;

int main() {
  // 우선순위 큐를 <자료형, 구현체, 비교연산자> 를 이용하여 선언한다.
  // 비교연산자에 less<int>를 사용하여 int가 큰값이 우선한다.
  priority_queue <int, vector<int>, less<int> > pq;
  
  pq.push(5);
  pq.push(3);
  pq.push(6);
  pq.push(7);

  while(!pq.empty()) {
    int temp = pq.top();
    cout << temp;
    pq.pop();
  }
  // 출력결과
  // 7653
  return 0;
}

오름차순

greater<int>

#include <queue>
#include <iostream>
using namespace std;

int main() {
  // 우선순위 큐를 <자료형, 구현체, 비교연산자> 를 이용하여 선언한다.
  // 비교연산자에 greater<int>를 사용하여 int가 작은값이 우선한다.
  priority_queue <int, vector<int>, greater<int> > pq;
  
  pq.push(5);
  pq.push(3);
  pq.push(6);
  pq.push(7);

  while(!pq.empty()) {
    int temp = pq.top();
    cout << temp;
    pq.pop();
  }
  // 출력결과
  // 3567
  return 0;
}

 

결론

sort와 pq는 서로 정렬에 사용되는 비교연산자가 반대이다.

실제로 커스텀 비교연산자를 이용해서 정렬을 하는 경우에도 똑같다. 

compare 함수를 선언해 sort에서 내림차순을 구현했다면, pq에서는 오름차순으로 적용된다.

이 점을 유의해서 sort와 pq를 자유자재로 써보자.