C++에서 주어진 숫자의 자릿수를 사용하여 구성할 수 있는 최대 숫자 찾기

n개의 숫자가 있다고 가정합니다. 그 숫자의 모든 자릿수를 사용하여 얻을 수 있는 최대 숫자를 찾아야 합니다. 따라서 숫자가 339625라면 최대 숫자는 965332가 될 수 있습니다.

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

예시

#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']++;
   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