주어진 수를 배열하여 가장 큰 수를 만드시겠습니까?

여기서는 주어진 수를 재배열하여 가장 큰 수를 생성하는 방법을 살펴보겠습니다. {45, 74, 23}이 주어졌다고 가정하면 프로그램은 가장 큰 수, 즉 744523을 찾습니다. 따라서 각 자릿수는 정렬되지 않습니다. 그러나 가장 큰 수를 만들기 위해 정수를 배치합니다.

이 문제를 해결하기 위해 문자열 정렬을 사용합니다. 그러나 비교 논리는 다릅니다. 비교 함수는 두 개의 숫자와 b를 취하여 연결하여 ab와 ba를 형성합니다. 그 중 어느 것이 더 큰지 고려합니다.

알고리즘

문자열 비교(a, b)

begin
   ab := concatenate b with a
   ba := concatenate a with b
   compare ba with ab, then return 1 if ba is bigger, otherwise return 0
end
getLargest(arr):
begin
   sort the arr with the comparison logic using compareString()
   for each string s in arr, do
      print s
   done
end

예시

#include<iostream>
#include <string>
#include &t;vector>
#include <algorithm>
using namespace std;
int stringCompare(string a, string b) {
   string ab = a.append(b);
   string ba = b.append(a);
   return ab.compare(ba) > 0 ? 1: 0;
}
void getLargest(vector<string> arr) {
   sort(arr.begin(), arr.end(), stringCompare); //sort the array
   for (int i =0; i < arr.size() ; i++ )
      cout << arr[i];
}
int main() {
   vector<string> arr;
   arr.push_back("45");
   arr.push_back("74");
   arr.push_back("23");
   getLargest(arr);
}

출력

744523