이 문제에서는 양의 정수가 주어집니다. 우리의 임무는 최대 한 번의 스왑 작업을 사용하여 더 작은 수를 형성하는 프로그램을 만드는 것입니다.
기존 번호의 자릿수를 사용하여 새 번호를 생성합니다. 형성된 가장 작은 숫자는 기존 숫자에서 한 자리만 바꿀 수 있습니다.
문제를 이해하기 위해 예를 들어보겠습니다.
Input: n = 63519 Output: 36519
솔루션 접근 방식
문제를 해결하는 한 가지 방법은 주어진 숫자의 자릿수 쌍을 교환하여 생성된 모든 숫자를 찾는 것입니다. 이 교환된 모든 숫자 중에서 가장 작은 숫자가 반환됩니다. 이를 위해 숫자를 문자열로 변환하고 위치를 교환합니다.
예시
솔루션 작동을 설명하는 프로그램
#include <iostream>
using namespace std;
int findSmallestNumSwapDig(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 smallest number created by swapping one digit is "<<findSmallestNumSwapDig(num) << endl;
return 0;
} 출력
The number is 792156 The smallest number created by swapping one digit is192756
또 다른 접근 방식
문제를 해결하는 또 다른 방법은 추가 보조 배열 aux[]를 사용하는 것입니다. 이 배열은 현재 인덱스의 오른쪽(큰 인덱스)에 가장 작은 숫자의 인덱스를 저장하는 데 사용됩니다. 즉, aux[i]는 숫자 자릿수의 오른쪽에 있는 가장 작은 숫자의 인덱스입니다. 해당 숫자가 없으면 aux[i] =-1을 초기화합니다. 이제 인덱스 0에서 n-1까지 숫자를 탐색하고 aux[] 배열에서 현재 값보다 작은 숫자를 찾습니다. 인덱스 0 값의 경우 0이 아닌 요소를 확인하고 0이 발생하면 값을 버립니다. 요소가 발견되면 arr[i] 및 arr[aux[i]]를 교환합니다. 생성된 번호를 반환합니다.
예시
솔루션 작동을 설명하는 프로그램
#include <bits/stdc++.h>
using namespace std;
int findSmallestNumSwapDig(int N){
string num = to_string(N);
int n = num.size();
int auxArr[n], right;
auxArr[n - 1] = -1;
right = n - 1;
for (int i = n - 2; i >= 1; i--) {
if (num[i] >= num[right])
auxArr[i] = right;
else {
if (num[i] == num[i + 1])
auxArr[i] = right;
else {
auxArr[i] = -1;
right = i;
}
}
}
int small = -1;
for (int i = 1; i < n; i++)
if (num[i] != '0') {
if (small == -1) {
if (num[i] < num[0])
small = i;
}
else if (num[i] <= num[small])
small = i;
}
if (small != -1)
swap(num[0], num[small]);
else {
for (int i = 1; i < n; i++) {
if (auxArr[i] != -1 && num[i] != num[auxArr[i]]) {
swap(num[i], num[auxArr[i]]);
break;
}
}
}
return stoi(num);
}
int main(){
int num = 792156;
cout<<"The number is "<<num<<endl;
cout<<"The smallest number created by swapping one digit is" <<findSmallestNumSwapDig(num)<< endl;
return 0;
} 출력
The number is 792156 The smallest number created by swapping one digit is192756