숫자 n이 주어지면 결과 숫자가 숫자 n보다 크도록 숫자의 두 자리를 바꿉니다. 가능하지 않으면 -1을 인쇄하십시오. 예를 들어 보겠습니다.
입력
12345
출력
12354
숫자 4와 5를 교환했습니다. 그리고 한 번의 교환으로 더 높은 숫자를 얻었습니다.
알고리즘
-
숫자의 자릿수가 내림차순이면 수를 만들 수 없습니다.
-
숫자의 오른쪽에서 마지막 숫자보다 작은 숫자의 인덱스를 찾습니다.
-
이전 숫자보다 크고 모든 숫자보다 작은 숫자의 인덱스를 찾습니다.
-
두 자리를 바꾸고 새 번호를 반환합니다.
- 새 번호를 반환합니다.
구현
다음은 위의 알고리즘을 C++로 구현한 것입니다.
#include <bits/stdc++.h>
using namespace std;
string getNextHigherNumber(string num) {
int len = num.size();
int firstDigitIndex = -1;
for (int i = len - 2; i >= 0; i--) {
if (num[i] < num[len - 1]) {
firstDigitIndex = i;
break;
}
}
if (firstDigitIndex == -1) {
return "-1";
}
int secondDigitIndex = -1;
for (int i = len - 1; i > firstDigitIndex; i--) {
if (num[i] > num[firstDigitIndex]) {
if (secondDigitIndex == -1 || num[i] <= num[secondDigitIndex]) {
secondDigitIndex = i;
}
}
}
char temp = num[firstDigitIndex];
num[firstDigitIndex] = num[secondDigitIndex];
num[secondDigitIndex] = temp;
return num;
}
int main() {
string num = "12345";
cout << "Given number: " << num << endl;
cout << "Next higher number: " << getNextHigherNumber(num) << endl;
return 0;
} 출력
위의 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
Given number: 12345 Next higher number: 12354