이 튜토리얼에서는 주어진 숫자 n보다 작으면서, 단 한 번의 자리 교환(swap) 연산만으로 만들 수 있는 가장 큰 숫자를 찾는 프로그램을 C++로 작성해 보겠습니다.
문제 해결 접근 방법
핵심 아이디어는 숫자를 오른쪽에서 왼쪽으로 훑어보며 처음으로 자릿수가 감소하는 지점을 찾는 것입니다. 이 지점의 자릿수를 오른쪽 구간에 있는 적절한 자릿수와 교환하면, 원래 숫자보다 작으면서도 가능한 한 큰 값을 얻을 수 있습니다.
단계별로 살펴보면 다음과 같습니다.
- 숫자 n을 문자열 형태로 초기화합니다.
- 문자열 끝에서부터 앞쪽으로 탐색하면서, 현재 자릿수가 바로 오른쪽 자릿수보다 큰 첫 번째 위치(index)를 찾아 변수에 저장합니다. 찾는 즉시 반복문을 종료합니다.
- 문자열 끝부터 위에서 찾은 index까지 다시 탐색하면서, index 위치의 자릿수보다 작으면서 후보들 중에서는 가장 큰 자릿수의 위치(smallerDigitIndex)를 찾습니다.
- 두 위치의 자릿수를 서로 교환(swap)한 뒤, 갱신된 숫자를 반환합니다.
- 교환 가능한 조건을 만족하지 않으면 "-1"을 반환합니다.
예제 코드
위 알고리즘을 C++로 구현한 코드입니다.
#include <bits/stdc++.h>
using namespace std;
string getTheNumber(string str) {
int length = str.length();
int index = -1;
// 오른쪽에서 왼쪽으로 탐색하며 감소하는 지점을 찾음
for (int i = length - 2; i >= 0; i--) {
if (str[i] > str[i+1]) {
index = i;
break;
}
}
// index보다 작으면서 후보 중 가장 큰 자릿수의 위치를 찾음
int smallerDigitIndex = -1;
for (int i = length - 1; i > index; i--) {
if (str[i] < str[index]) {
if (smallerDigitIndex == -1 || str[i] >= str[smallerDigitIndex]) {
smallerDigitIndex = i;
}
}
}
if (index == -1) {
return "-1";
}
if (smallerDigitIndex != -1) {
swap(str[index], str[smallerDigitIndex]);
return str;
}
return "-1";
}
int main() {
string str = "54624";
cout << getTheNumber(str) << endl;
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
54426
동작 과정 상세 설명
입력이 "54624"일 때 알고리즘이 어떻게 동작하는지 살펴보겠습니다.
- 오른쪽에서 왼쪽으로 탐색하면, 인덱스 2의 자릿수 '6'이 오른쪽 자릿수 '2'보다 큰 첫 번째 감소 지점입니다. 따라서 index = 2가 됩니다.
- 이후 인덱스 2보다 오른쪽 구간("24")에서 '6'보다 작으면서 가장 큰 자릿수는 인덱스 4의 '4'입니다.
- '6'과 '4'를 교환하면 "54426"이 되고, 이것이 한 번의 스왑으로 만들 수 있는 n보다 작은 수 중 최댓값입니다.
만약 숫자의 자릿수가 왼쪽부터 오른쪽으로 계속 증가하는 형태(예: "12345")라면, 어떤 스왑을 하더라도 더 작은 수를 만들 수 없으므로 "-1"이 반환됩니다.
마무리
이번 튜토리얼에서는 한 번의 스왑 연산만으로 만들 수 있는 n 미만의 최댓값을 찾는 방법을 알아보았습니다. 시간 복잡도는 문자열 길이에 대해 선형적인 O(n)입니다. 튜토리얼에 대해 궁금한 점이 있다면 댓글로 남겨주세요.