이 문제에서는 양의 정수가 주어집니다. 우리의 임무는 최대 한 번의 스왑 작업을 사용하여 가장 큰 수를 형성하는 프로그램을 만드는 것입니다.
기존 번호의 자릿수를 사용하여 새 번호를 생성합니다.
형성된 가장 큰 숫자는 기존 숫자에서 한 자리만 바꿀 수 있습니다.
문제를 이해하기 위해 예를 들어보겠습니다.
Input: n = 63512 Output: 65312
솔루션 접근 방식
문제를 해결하는 한 가지 방법은 주어진 숫자의 자릿수 쌍을 교환하여 생성된 모든 숫자를 찾는 것입니다. 이 교환된 모든 숫자 중에서 가장 큰 숫자가 반환됩니다. 이를 위해 숫자를 문자열로 변환하고 위치를 교환합니다.
예시
솔루션 작동을 설명하는 프로그램
#include <iostream>
using namespace std;
int findLargestNumSwapDig(int N){
string strNum = to_string(N);
string temp = strNum;
for (int i = 0; i < strNum.size(); i++) {
for (int j = i + 1; j < strNum.size(); j++) {
swap(strNum[i], strNum[j]);
if (stoi(strNum) > stoi(temp))
temp = strNum;
swap(strNum[i], strNum[j]);
}
}
return stoi(temp);
}
int main(){
int num = 792156;
cout<<"The number is "<<num<<endl;
cout<<"The largest number created by swapping one digit is "<<findLargestNumSwapDig(num) << endl;
return 0;
} 출력
The number is 792156 The largest number created by swapping one digit is972156
또 다른 접근 방식
문제를 해결하는 또 다른 방법은 가능한 가장 큰 수에 기여하는 스왑을 찾는 것입니다. 이를 위해 왼쪽에서 오른쪽으로 숫자를 스캔합니다. 그런 다음 다음 숫자가 이전 숫자보다 큰 첫 번째 쌍을 교환합니다. 이 교환은 가장 큰 숫자가 됩니다.
예시
솔루션 작동을 설명하는 프로그램
#include <iostream>
using namespace std;
int findLargestNumSwapDig(int N){
int currMaxDig = -1;
int currMaxInd = -1;
int lSwap = -1;
int rSwap = -1;
string strNum = to_string(N);
for (int i = strNum.size() - 1; i >= 0; i--) {
if (strNum[i] > currMaxDig) {
currMaxDig = strNum[i];
currMaxInd = i;
continue;
}
if (strNum[i] < currMaxDig) {
lSwap = i;
rSwap = currMaxInd;
}
}
if (lSwap == -1)
return N;
swap(strNum[lSwap], strNum[rSwap]);
return stoi(strNum);
}
int main(){
int num = 792156;
cout<<"The number is "<<num<<endl;
cout<<"The largest number created by swapping one digit is "<<findLargestNumSwapDig(num) << endl;
return 0;
} 출력
The number is 792156 The largest number created by swapping one digit is972156