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

숫자 배열이 있다고 가정합니다. 배열의 모든 자릿수를 사용하여 얻을 수 있는 최대 수를 찾아야 합니다. 따라서 배열이 [3, 3, 9, 6, 2, 5]와 같으면 최대 개수는 965332가 될 수 있습니다.

문제에서 숫자를 증가하지 않는 순서로 쉽게 정렬한 다음 인쇄할 수 있음을 알 수 있습니다. 그러나 보다 효율적인 방법을 사용하여 이 문제를 해결할 수 있습니다. 크기가 10인 배열 하나를 만들어 각 숫자의 빈도를 저장한 다음 그에 따라 9에서 0까지의 숫자를 인쇄할 수 있습니다.

예

#include <iostream>
#include <string>
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 = res + (i * mul);
         freq[i]--;
         mul = 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);
}

출력

Maximum number: 965332