이 튜토리얼에서는 주어진 숫자의 자릿수를 단 한 번 교환(swap)했을 때 얻을 수 있는 가장 큰 수를 찾는 프로그램을 C++로 작성해 보겠습니다.
핵심 아이디어는 간단합니다. 숫자를 문자열로 변환한 뒤, 오른쪽(끝)에서부터 왼쪽으로 탐색하면서 가장 큰 자릿수를 기록하고, 그보다 작은 자릿수가 나타나면 두 위치를 서로 교환하는 것입니다.
문제 해결 절차
- 숫자 n을 초기화합니다.
- 정수를 문자열로 변환합니다.
- 문자열의 끝에서부터 시작하는 반복문을 작성합니다.
- 현재까지의 최대 자릿수와 해당 인덱스를 저장합니다.
- 현재 자릿수가 최대 자릿수보다 작다면, 시작 인덱스를 현재 인덱스로, 끝 인덱스를 최대 자릿수 인덱스로 업데이트합니다.
- 반복문이 끝난 후 시작 인덱스가 여전히 -1이라면, 이미 내림차순으로 정렬된 수이므로 n을 그대로 반환합니다.
- 그렇지 않으면 시작 인덱스와 끝 인덱스에 있는 두 자릿수를 교환합니다.
- 문자열을 다시 정수로 변환하여 결과를 반환합니다.
뒤에서부터 탐색하는 이유는, 같은 값의 최대 자릿수가 여러 개 있을 때 가장 오른쪽(일의 자리에 가까운)에 있는 최대값과 앞의 작은 자릿수를 교환해야 결과가 가장 커지기 때문입니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
int getLargestNumber(int n) {
int maxDigit = -1;
int maxDigitIndex = -1;
int startIndex = -1;
int endIndex = -1;
string nInStr = to_string(n);
for (int i = nInStr.size() - 1; i >= 0; i--) {
if (nInStr[i] > maxDigit) {
maxDigit = nInStr[i];
maxDigitIndex = i;
continue;
}
if (nInStr[i] < maxDigit) {
startIndex = i;
endIndex = maxDigitIndex;
}
}
if (startIndex == -1) {
return n;
}
swap(nInStr[startIndex], nInStr[endIndex]);
return stoi(nInStr);
}
int main() {
int n = 678;
cout << getLargestNumber(n) << endl;
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
876
입력이 678인 경우, 맨 앞의 6과 맨 뒤의 8을 교환하여 876이라는 가장 큰 수를 만들게 됩니다.
마무리
이번 튜토리얼에서는 문자열 탐색과 자릿수 교환을 활용해 한 번의 swap으로 만들 수 있는 최댓값을 구하는 방법을 살펴보았습니다. 이 알고리즘은 시간 복잡도 O(d)(d는 자릿수)로 매우 효율적입니다. 튜토리얼에 대해 궁금한 점이 있다면 댓글로 남겨주세요.