[C++] sort()의 비교 함수자 제대로 알기 - 오름차순 vs 내림차순

문제 소개

https://www.acmicpc.net/problem/1427

숫자의 각 자릿수를 내림차순으로 정렬 하는 문제를 풀다가 greater<T>()에 대해 자세히 알아보게 되었다.

위 문제는 예를 들어 입력값이 2143이라면, 각 자릿수 '2', '1', '4', '3'을 내림차순으로 정렬해 4321로 출력하는 문제다.
문자열로 변환한 뒤 sort() 함수의 3번째 인자로 greater<char>()를 함께 넘기면 된다는 것을 알게 되었지만, 왜 그렇게 동작하는지 정확히 이해하고 싶었다.

이 글에서는 STL의 greater<T>()가 어떻게 동작하는지 , 그리고 sort() 함수에서 어떻게 내림차순을 만들 수 있는지 정리해 본다.

[C++]

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    string N;
    cin >> N;

    sort(N.begin(), N.end(), greater<char>());

    cout << N;

    return 0;
}

수 N을 string으로 받아 각 문자(char)를 정렬할 계획을 짰다.
이때 내림차순이라는 기준으로 사용된 것이 greater<char>()였다.

greater<T>()란?

C++ STL의 greater<T>는 함수 객체(Function Object) 로, 두 값 a, b를 받아 a > b 를 반환하는 구조체이다.

template <class T>
struct greater {
    bool operator()(const T& a, const T& b) const {
        return a > b;
    }
};

즉, 정렬 시 a > b이면 a를 앞에 배치 -> 내림차순 정렬이 된다.

함수 객체(Function Object)란?

() 연산자(함수 호출 연산자)를 오버로드한 클래스의 인스턴스로, 함수처럼 동작하는 객체이다.
객체인데 함수처럼 사용할 수 있는 것으로 보면 된다.

예제. 함수 객체 직접 만들어 보기

#include <iostream>
using namespace std;

struct Add {
    int operator()(int a, int b) const {
        return a + b;
    }
};

int main() {
    Add add;     // 함수 객체 생성

    cout << add(3, 5);     // 함수처럼 호출 가능

    return 0;
}

🔽 출력 :

8

Add는 () 연산자를 오버로드했기 때문에 함수처럼 add(3, 5)로 사용할 수 있다.
이것이 함수 객체이다. 함수와는 달리 멤버 변수를 가져 상태를 저장할 수 있다는 장점이 있다.

대표적인 함수 객체로는 equal_to<T>() 같은 것이 있다.

sort() 함수의 정렬 기준 바꾸기

기본적인 std::sort()는 오름차순 정렬을 수행한다.

sort(v.begin(), v.end());

우리가 자주 쓰는 sort 함수인데, 이 sort 함수에는 3번째 인자가 생략되어 있다.
sort() 함수의 3번째 인자에는 비교자가 들어가는데, 3번째 인자를 생략하면 default로 less<T>()가 들어간다.

std::sort의 비교 방식

std::sort(first, last, comp);

여기서 comp은 비교 함수 객체이고 함수처럼 호출할 수 있다.

comp(a, b)는 이렇게 해석된다.

a는 b보다 앞에 와야 하는가? 참이면 a는 b보다 앞에 와야 한다.

즉, comp(a, b) == true이면 a는 b보다 앞에 와야 한다는 뜻이다.

less<T>()란?

less<T>()는 C++ STL에서 제공하는 함수 객체(Function Object) 중 하나로, 비교 대상 a, b에 대해 a < b 를 반환하는 객체이다.
즉, less<T>()는 작은 값이 앞에 오도록 하는 오름차순 정렬 을 위한 기본 비교자이다.

template <class T>
struct less {
    bool operator()(const T& a, const T& b) const {
        return a < b;
    }
};

operator()를 정의한 함수 객체이기 때문에 함수처럼 사용할 수 있는 객체이다.

예제 코드로 이해하기

비교 기준을 바꾸고 싶을 때는 함수 객체를 세 번째 인자로 넘긴다.

예제 1. 오름차순 정렬 (기본)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {3, 1, 4, 1, 5};

    sort(v.begin(), v.end());     // 기본 정렬 : less<int>()

    for (int i : v)
        cout << i << " ";
}

🔽 출력 :

1 1 3 4 5

예제 2. 내림차순 정렬 (greater<T>())

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {3, 1, 4, 1, 5};

    sort(v.begin(), v.end(), greater<int>());

    for (int i : v)
        cout << i << " ";
}

🔽 출력 :

5 4 3 1 1

요약

이름	의미	비교 방식	정렬 결과
less<T>() (기본)	오름차순	a < b	작은 값이 앞에 옴
greater<T>()	내림차순	a > b	큰 값이 앞에 옴

마무리

greater<T>()는 정렬 기준을 내림차순으로 바꾸고 싶을 때 가장 직관적으로 사용할 수 있는 도구다.
함수 객체의 개념을 이해하면 STL의 다양한 알고리즘 함수들을 더욱 유연하게 활용할 수 있다.