C++에서 주어진 자릿수로 만들 수 있는 가장 큰 수 찾기

자릿수(digit)로 이루어진 배열이 하나 주어져 있다고 가정해 봅시다. 이 배열의 모든 자릿수를 한 번씩 사용하여 만들 수 있는 최댓값을 찾아야 합니다. 예를 들어 배열이 [3, 3, 9, 6, 2, 5]라면, 만들 수 있는 최대 수는 965332입니다.

접근 방법

이 문제는 자릿수를 내림차순으로 정렬한 뒤 차례대로 이어 붙이면 간단히 해결할 수 있습니다. 하지만 정렬 대신 더 효율적인 방법을 사용할 수 있습니다.

핵심 아이디어는 크기가 10인 빈도(frequency) 배열을 활용하는 것입니다.

입력 배열을 한 번 순회하면서 각 자릿수(0~9)의 등장 횟수를 기록합니다.
작은 자릿수부터 낮은 자리(일의 자리)에 배치하고, 큰 자릿수는 점점 높은 자리로 옮깁니다. 이를 위해 결과 값에 '자릿수 × 10의 거듭제곱'을 더하며 누적합니다.

즉, 0부터 9까지 순회하면서 해당 자릿수가 남아 있는 동안 곱셈 인자(mul)를 10배씩 계속 늘려가며 더해주면, 자연스럽게 가장 큰 자릿수가 가장 높은 자리에 위치하게 되어 전체적으로 최댓값이 완성됩니다.

C++ 구현 코드

#include <iostream>
using namespace std;

int maxNumFromNum(int arr[], int n) {
    int freq[10] = {0};

    // 각 자릿수의 빈도 계산
    for (int i = 0; i < n; i++)
        freq[arr[i]]++;

    int res = 0, mul = 1;

    // 작은 자릿수부터 낮은 자리에 배치
    for (int i = 0; i <= 9; i++) {
        while (freq[i] > 0) {
            res += i * mul;
            freq[i]--;
            mul *= 10;
        }
    }
    return res;
}

int main() {
    int digits[] = {3, 3, 9, 6, 2, 5};
    int n = sizeof(digits) / sizeof(digits[0]);

    cout << "Maximum number: " << maxNumFromNum(digits, n);
    return 0;
}

출력 결과

Maximum number: 965332

동작 원리 살펴보기

예제 입력 [3, 3, 9, 6, 2, 5]의 경우 빈도 배열에는 2가 1개, 3이 2개, 5가 1개, 6이 1개, 9가 1개 저장됩니다. 이후 다음과 같이 누적 계산이 진행됩니다.

2×1 + 3×10 + 3×100 + 5×1000 + 6×10000 + 9×100000 = 965332

작은 숫자가 낮은 자리에, 큰 숫자가 높은 자리에 배치되므로 결과적으로 가능한 최댓값이 만들어집니다.

시간 및 공간 복잡도

시간 복잡도: O(n) — 입력 배열을 한 번 순회하며 빈도를 세고, 빈도 배열 순회는 최대 10번으로 상수 시간입니다.
공간 복잡도: O(1) — 크기 10의 고정 배열만 추가로 사용합니다.

참고로 자릿수의 개수가 많아지면 결과 값이 int 범위를 초과할 수 있으므로, 실제 서비스 환경에서는 long long 타입을 사용하는 것이 안전합니다.