C++로 자릿수를 재배열해 만들 수 있는 최대 숫자 구하기

문제 개요

n자리 숫자가 하나 주어졌다고 가정해 봅시다. 이때 해당 숫자의 모든 자릿수를 그대로 사용하여 만들 수 있는 최댓값을 찾아야 합니다.

예를 들어 입력이 339625라면, 각 자릿수(3, 3, 9, 6, 2, 5)를 재배열하여 얻을 수 있는 최대 숫자는 965332입니다.

접근 방법

가장 직관적인 방법은 자릿수들을 내림차순으로 정렬한 뒤 출력하는 것입니다. 하지만 정렬 알고리즘은 일반적으로 O(n log n)의 시간 복잡도를 가지므로, 더 효율적인 방법을 사용할 수 있습니다.

핵심 아이디어는 다음과 같습니다.

크기가 10인 배열을 만들어 각 자릿수(0~9)의 등장 횟수(빈도)를 저장합니다.
9부터 0까지 차례대로 순회하면서, 해당 자릿수가 남아 있는 만큼 결과에 이어 붙입니다.

이 방식은 계수 정렬(counting sort)과 유사한 원리로 동작하며, 시간 복잡도는 자릿수 길이에 비례하는 O(d)(d는 자릿수 개수)로 매우 효율적입니다.

C++ 구현 예제

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

int maxNumFromNum(int num) {
    int freq[10] = {0};
    string str = to_string(num);
    
    // 각 자릿수의 빈도 계산
    for (int i = 0; i < str.length(); i++)
        freq[str[i] - '0']++;
    
    // 0부터 9까지 순서대로 결과 조합
    // 작은 자릿수부터 곱셈 위치를 잡으면 최종적으로 내림차순이 됨
    int res = 0, mul = 1;
    for (int i = 0; i <= 9; i++) {
        while (freq[i] > 0) {
            res = res + (i * mul);
            freq[i]--;
            mul = mul * 10;
        }
    }
    return res;
}

int main() {
    int num = 339625;
    cout << "Maximum number: " << maxNumFromNum(num);
}

실행 결과

Maximum number: 965332

동작 원리 설명

위 코드에서는 0부터 9까지 오름차순으로 순회하면서, 현재 자릿수를 결과 값에 더할 때마다 자릿값(mul)을 10배씩 늘려갑니다. 이렇게 하면 나중에 처리되는 큰 숫자일수록 높은 자릿수에 배치되므로, 최종 결과는 자연스럽게 내림차순으로 정렬된 최댓값이 됩니다.

예를 들어 339625의 경우:

빈도 배열에는 2가 1개, 3이 2개, 5가 1개, 6이 1개, 9가 1개 저장됩니다.
0부터 차례대로 처리하면 2 → 3 → 3 → 5 → 6 → 9 순서로 낮은 자릿수부터 채워집니다.
최종적으로 965332라는 최댓값이 완성됩니다.

마무리

정렬 대신 빈도 배열을 활용하면 불필요한 비교 연산 없이 선형 시간 안에 문제를 해결할 수 있습니다. 자릿수 처리 문제에서 빈도 카운팅 기법은 매우 유용하게 활용되는 패턴이므로, 다양한 변형 문제에도 응용해 보시기 바랍니다.