C++에서 자릿수 합을 기준으로 숫자 정렬하는 방법

이 글에서는 각 숫자의 자릿수 합을 기준으로 배열을 정렬하는 방법을 알아봅니다. 자릿수의 합이 작은 숫자가 앞에 오고, 합이 큰 숫자일수록 뒤에 배치됩니다.

문제 이해하기

예를 들어 다음과 같은 데이터가 있다고 가정해 보겠습니다.

data = {14, 129, 501, 23, 0, 145}

각 숫자의 자릿수 합은 다음과 같습니다.

• 0 → 0
• 14 → 1 + 4 = 5
• 23 → 2 + 3 = 5
• 501 → 5 + 0 + 1 = 6
• 145 → 1 + 4 + 5 = 10
• 129 → 1 + 2 + 9 = 12

따라서 자릿수 합을 기준으로 정렬하면 결과는 다음과 같습니다.

data = {0, 14, 23, 501, 145, 129}

C++ STL의 sort() 함수는 기본적으로 오름차순 정렬을 수행하지만, 세 번째 인자로 사용자 정의 비교 함수(comparator)를 전달하면 원하는 기준으로 정렬할 수 있습니다. 여기서는 '자릿수 합이 작은 숫자가 앞에 온다'는 비교 로직을 직접 만들어 적용합니다.

알고리즘

compare(num1, num2):
시작
    if num1의 자릿수 합 < num2의 자릿수 합, then
        return 1   // num1이 앞에 옴
    return 0
종료

C++ 구현 예제

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

// 숫자의 자릿수 합을 계산하는 함수
int sumOfDigits(int n){
    int sum = 0;
    while(n){
        sum += n % 10;
        n /= 10;
    }
    return sum;
}

// 사용자 정의 비교 함수
int compare(int num1, int num2){
    if(sumOfDigits(num1) < sumOfDigits(num2))
        return 1;
    return 0;
}

int main(){
    int data[] = {14, 129, 501, 23, 0, 145};
    int n = sizeof(data)/sizeof(data[0]);

    sort(data, data + n, compare);

    for(int i = 0; i<n; i++){
        cout << data[i] << " ";
    }
}

실행 결과

0 14 23 501 145 129

코드 설명

sumOfDigits() 함수는 나눗셈과 나머지 연산(%, /)을 반복하면서 각 자릿수를 추출해 더합니다. 예를 들어 129가 입력되면 9 + 2 + 1 = 12를 반환합니다.

compare() 함수는 두 숫자의 자릿수 합을 비교하여, 첫 번째 숫자의 합이 더 작으면 참(1)을 반환합니다. STL의 sort() 함수는 이 비교 함수의 반환값을 보고 요소들의 순서를 결정하므로, 최종적으로 자릿수 합이 작은 순서대로 배열이 정렬됩니다.

참고로 C++11 이상에서는 람다 표현식을 사용해 비교 함수를 더 간결하게 작성할 수도 있습니다.

sort(data, data + n, [](int a, int b){
    return sumOfDigits(a) < sumOfDigits(b);
});