C++로 숫자의 다음 순열 구하기: 알고리즘 설명과 구현 예제

문제 소개

어떤 수 n이 주어졌을 때, 자릿수를 재배열하여 만들 수 있는 숫자 중 현재 값보다 바로 다음으로 큰 순열을 구하는 프로그램을 작성해야 합니다. 만약 n이 이미 내림차순으로 배치된, 즉 가장 큰 순열이라면 다시 가장 작은 순열(오름차순)로 되돌려 순환시킵니다.

예를 들어 입력이 n = 319라면, 자릿수 {3, 1, 9}로 만들 수 있는 조합 중 319 다음으로 큰 수는 391이므로 출력은 391이 됩니다.

해결 전략

이 문제는 널리 알려진 '다음 순열(Next Permutation)' 알고리즘을 응용하여 해결할 수 있으며, 세 가지 보조 함수를 정의한 뒤 메인 로직에서 조합하는 방식으로 풀이합니다.

1. makeArray() – 숫자를 자릿수 배열로 변환

정수 x를 매개변수로 받습니다.
x가 0이 아닌 동안 x mod 10(마지막 자릿수)을 배열 끝에 추가하고, x를 10으로 나누는 작업을 반복합니다.
이 과정이 끝나면 자릿수가 역순으로 저장되어 있으므로 배열을 뒤집어 올바른 순서로 만든 뒤 반환합니다.

2. combine() – 자릿수 배열을 정수로 변환

배열 v를 매개변수로 받고 결과값 ret을 0으로 초기화합니다.
배열의 각 원소 i에 대해 ret = ret * 10 + i를 반복 적용합니다.
완성된 정수를 반환합니다.

3. getIndex() – 교환 지점(피벗) 찾기

배열 v를 매개변수로 받고 결과값 ret을 -1로 초기화합니다.
배열의 뒤쪽부터 앞쪽으로 탐색하며, 처음으로 v[i] > v[i-1]이 성립하는 인덱스 i를 찾으면 ret에 저장하고 반복을 종료합니다.
ret이 -1이 아니라면(교환 지점이 존재한다면):
- 기준값 x = v[ret - 1]을 저장합니다.
- ret + 1부터 배열 끝까지 탐색하며, v[j] < v[idx]이면서 동시에 v[j] > x를 만족하는 원소의 인덱스를 idx로 갱신합니다. 즉, 기준값보다 크면서 후보 중 가장 작은 값(오른쪽에 있는 값)을 찾는 것입니다.
- v[ret - 1]과 v[idx]를 서로 교환(swap)합니다.
마지막으로 ret을 반환합니다.

메인 로직 (solve)

makeArray(num)으로 숫자를 자릿수 배열 v로 변환합니다.
getIndex(v)로 교환 지점 idx를 구합니다.
idx == -1이라면 숫자가 이미 최대 순열이므로 배열 전체를 오름차순으로 정렬하여 최소 순열로 되돌립니다.
그렇지 않다면 피벗 뒤쪽 구간(v.begin() + idx부터 끝까지)만 오름차순으로 정렬합니다. 교환 후 뒷부분은 내림차순이므로, 이 구간만 정렬하면 같은 접두사를 가진 순열 중 가장 작은 꼬리가 만들어져 '바로 다음' 순열이 됩니다.
combine(v)으로 배열을 다시 정수로 합쳐 반환합니다.

C++ 구현 예제

다음 구현을 통해 더 잘 이해할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   vector<int> makeArray(int x) {
      vector<int> ret;
      while (x) {
         ret.push_back(x % 10);
         x /= 10;
      }
      reverse(ret.begin(), ret.end());
      return ret;
   }
   int combine(vector<int>& v) {
      int ret = 0;
      for (int i : v) {
         ret *= 10;
         ret += i;
      }
      return ret;
   }
   int getIndex(vector<int>& v) {
      int ret = -1;
      for (int i = v.size() - 1; i >= 1; i--) {
         if (v[i] > v[i - 1]) {
            ret = i;
            break;
         }
      }
      if (ret != -1) {
         int x = v[ret - 1];
         int idx = ret;
         for (int j = ret + 1; j < v.size(); j++) {
            if (v[j] < v[idx] && v[j] > x) {
               idx = j;
            }
         }
         swap(v[ret - 1], v[idx]);
      }
      return ret;
   }
   int solve(int num) {
      vector<int> v = makeArray(num);
      int idx = getIndex(v);
      if(idx == -1) {
         sort(v.begin(), v.end());
      }
      else {
         sort(v.begin() + idx, v.end());
      }
      return combine(v);
   }
};
int solve(int n) {
   return (new Solution())->solve(n);
}
int main(){
   int n = 319;
   cout << solve(n);
}

입력

출력

동작 과정 살펴보기

입력 319의 경우를 단계별로 살펴보면 다음과 같습니다.

자릿수 배열 생성: [3, 1, 9]
뒤에서부터 탐색: v[2]=9 > v[1]=1이므로 교환 지점 ret = 2
기준값 x = v[1] = 1, 뒤쪽 구간에서 x보다 큰 값 9와 교환 → [3, 9, 1]
피벗 위치(idx = 2)부터 끝까지 정렬 → [3, 9, 1] (이미 정렬된 상태)
배열을 정수로 결합 → 최종 결과 391