C++로 한 번의 스왑만 사용해 구하는 다음으로 큰 숫자

문제 소개

숫자 n이 주어졌을 때, 임의의 두 자릿수를 딱 한 번 교환(swap)하여 원래 수보다 더 큰 수를 만들어야 합니다. 만약 어떤 방법으로도 더 큰 수를 만들 수 없다면 -1을 출력합니다.

먼저 예시를 살펴보겠습니다.

입력

출력

위 예제에서는 4와 5의 자리를 서로 바꾸었습니다. 이처럼 단 한 번의 스왑만으로 원래 수보다 큰 12354를 얻을 수 있습니다.

알고리즘 접근 방식

핵심 아이디어는 다음과 같습니다.

모든 자릿수가 내림차순으로 배열되어 있다면(예: 54321) 어떤 두 자릿수를 교환해도 더 큰 수를 만들 수 없습니다. 이 경우 -1을 반환합니다.
오른쪽 끝부터 왼쪽으로 탐색하며, 마지막 자릿수보다 작은 첫 번째 자릿수의 인덱스를 찾습니다.
그 인덱스 오른쪽에 위치한 자릿수들 중에서, 앞서 찾은 자릿수보다 크면서 나머지 자릿수들 중 가장 작은 값인 자릿수의 인덱스를 찾습니다.
찾은 두 자릿수를 서로 교환하고, 그 결과로 얻은 새로운 숫자를 반환합니다.

C++ 구현

다음은 위 알고리즘을 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

복잡도 분석

이 알고리즘은 문자열을 최대 두 번 선형으로 훑기 때문에 시간 복잡도는 O(n)이며, 입력 문자열을 그대로 활용해 자릿수만 교환하므로 추가 메모리 사용량은 O(1)입니다. 즉, 매우 긴 숫자 문자열에 대해서도 효율적으로 동작합니다.