C++에서 동일한 자릿수로 N보다 작은 가장 큰 수 찾기

이 문제에서는 숫자를 나타내는 문자열 N이 제공됩니다. 우리의 임무는 동일한 자릿수로 N보다 작은 가장 큰 수를 찾는 것입니다.

문제 설명: 주어진 수의 N보다 작은 수 중 가장 큰 자릿수를 모두 사용하여 수를 찾아야 합니다.

문제를 이해하기 위해 예를 들어 보겠습니다.

입력: N ="54314"

출력: 54341

해결 방법

이 문제에 대한 간단한 해결책은 가장 큰 작은 숫자를 찾기 위해 이동할 수 있는 숫자의 자릿수를 찾는 것입니다. 이제 목적을 해결하기 위해서는 그 숫자가 올바른 성공보다 커야 합니다.

이를 위해 숫자 형식을 오른쪽에서 왼쪽으로 탐색하고 마지막 요소보다 큰 요소를 찾습니다.

그런 다음 오른쪽 부분배열에서 가장 큰 요소를 찾아 현재 요소로 바꿉니다. 정렬 후 하위 배열은 내림차순입니다. 이것은 가장 작은 요소가 될 것입니다.

우리 솔루션의 작동을 설명하는 프로그램,

예

#include <bits/stdc++.h>
using namespace std;

void calcGreatestSmallerElement(string N, int size) {
   
   int i, j;
   for (i = size - 1; i > 0; i--)
      if (N[i] < N[i - 1])
         break;

   if (i == 0) {
      cout << "Previous number is not possible";
      return;
   }

   int x = N[i - 1], greatest = i;
   for (j = i; j < size; j++)
      if (N[j] < x && N[j] > N[greatest])
         greatest = j;

   swap(N[greatest], N[i - 1]);
   sort(N.begin() + i, N.begin() + size, greater<char>());

   cout<<"The Greatest smaller number with same set of digits is "<<N;

   return;
}

int main() {
   
   string N = "654232";
   int size = N.length();
   cout<<"The number is "<<N<<endl;
   calcGreatestSmallerElement(N, size);

   return 0;
}

출력

The number is 654232
The Greatest smaller number with same set of digits is 654223