C++에서 일정한 순서로 숫자를 배열하여 가장 큰 숫자

이 문제에서는 숫자의 배열이 주어지고 특정 방식으로 변경하여 만들 수 있는 가장 큰 값을 찾아야 합니다. 배열의 조건은 짝수와 홀수의 순서가 동일하게 유지되어야 한다는 것입니다. 즉, 모든 짝수의 순서는 변경할 수 없습니다.

개념을 더 잘 이해하기 위해 예를 들어 보겠습니다.

Input : {17, 80, 99, 27, 14 , 22}
Output: 801799271422
Explanation: the order of Even and Odd numbers is :
Even : 80 14 22
Odd : 17 99 27

여기에서 99가 가장 큰 수이지만 홀수 순서로 17이 앞에 오기 때문에 80을 먼저 고려한 다음 - 80 17 99 27 14 22와 같은 배열 순서를 만듭니다.

문제를 이해했으므로 이에 대한 솔루션을 생성해 보겠습니다. 여기서 우리는 Even과 Odd의 시퀀스에 대한 제약 조건이 정의되어 있으므로 고전적인 내림차순으로 갈 수 없습니다. 따라서 우리는 이 순서를 유지하고 Even 및 Odd 순서의 첫 번째 요소 중 가장 큰 것을 확인해야 합니다. 그런 다음 그렇게 가십시오. 이를 보다 명확하게 해주는 알고리즘을 살펴보겠습니다.

알고리즘

Step 1 : Create two structures, one for even other for odd, this will maintain the sequence.
Step 2 : Take one element from each structure and check
         which combination makes a large number. Example, if E is
         the even number and O is the odd number which are at the
         top of the structure. then we will check which one is Greater of EO and OE.
Step 3 : Place the greater combination into the final sequence.
Step 4 : Print the final sequence.

예시

이제 이 알고리즘을 기반으로 프로그램을 만들어 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
string merge(vector<string> arr1, vector<string> arr2) {
   int n1 = arr1.size();
   int n2 = arr2.size();
   int i = 0, j = 0;
   string big = "";
   while (i < n1 && j < n2) {
      if ((arr1[i]+arr2[j]).compare((arr2[j]+arr1[i])) > 0)
         big += arr1[i++];
      else
         big += arr2[j++];
   }
   while (i < n1)
      big += arr1[i++];
   while (j < n2)
      big += arr2[j++] ;
   return big;
}
string largestNumber(vector<string> arr, int n) {
   vector<string> even, odd;
   for (int i=0; i<n; i++) {
      int lastDigit = arr[i].at(arr[i].size() - 1) - '0';
      if (lastDigit % 2 == 0)
         even.push_back(arr[i]);
      else
         odd.push_back(arr[i]);
   }
   string biggest = merge(even, odd);
   return biggest;
}
int main() {
   vector<string> arr;
   arr.push_back("17");
   arr.push_back("80");
   arr.push_back("99");
   arr.push_back("27");
   arr.push_back("14");
   arr.push_back("22");
   int n = arr.size();
   cout<<"Biggest possible number from the array is = "<<largestNumber(arr, n);
   return 0;
}

출력

Biggest possible number from the array is = 801799271422