C++로 같은 자릿수를 가진 다음으로 큰 수 찾는 방법

이 문제에서는 하나의 수 N이 주어집니다. 우리의 목표는 N과 동일한 자릿수 집합을 사용하면서 N보다 큰 수 중 가장 작은 수, 즉 '다음으로 큰 수'를 찾는 것입니다.

문제 이해를 위한 예시

입력

N = "92534"

출력

92543

92534와 같은 자릿수(9, 2, 5, 3, 4)로 만들 수 있는 수 중 92534보다 크면서 가장 작은 값이 92543이므로 정답은 92543입니다.

해결 접근 방법

다음으로 큰 수를 찾는 가장 간단한 방법은 다음 세 단계로 진행됩니다.

• 숫자를 최하위 자릿수부터 최상위 자릿수까지 순회하면서, 현재 자릿수가 바로 앞 자릿수보다 커지는 지점을 찾습니다. 이 지점이 교환의 기준이 됩니다.

• 그 지점 오른쪽에 있는 자릿수들 중에서 기준 자릿수보다 크면서 가장 작은 숫자를 찾아 기준 자릿수와 서로 교환(swap)합니다.

• 교환이 완료되면 기준 지점 이후의 나머지 부분 배열을 오름차순으로 정렬하여 결과를 반환합니다. 이렇게 하면 교환 후 남은 자릿수로 만들 수 있는 가장 작은 수가 보장됩니다.

만약 전체 숫자를 끝까지 순회했는데도 오름차순인 구간이 없다면(예: "54321"처럼 이미 내림차순으로 정렬된 경우), 더 큰 수를 만드는 것이 불가능하므로 적절한 메시지를 출력해야 합니다.

솔루션 구현 예제

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
void findNextGreater(char number[], int n) {
    int i, j;
    // 뒤에서부터 탐색하며 number[i] > number[i-1]인 지점 찾기
    for (i = n-1; i > 0; i--)
        if (number[i] > number[i-1])
            break;
    // 내림차순으로 정렬된 경우 다음 큰 수 없음
    if (i==0) {
        cout<<"Next number is not possible";
        return;
    }
    int x = number[i-1], smallest = i;
    // x보다 크면서 가장 작은 숫자 찾기
    for (j = i+1; j < n; j++)
        if (number[j] > x && number[j] < number[smallest])
            smallest = j;
    // 두 숫자 교환
    char temp = number[smallest];
    number[smallest] = number[i-1];
    number[i-1] = temp;
    // 나머지 부분 배열 오름차순 정렬
    sort(number + i, number + n);
    cout<<number;
    return;
}
int main(){
    char number[] = "92534";
    int n = strlen(number);
    cout<<"The next number with same set of digits is ";
    findNextGreater(number, n);
    return 0;
}

실행 결과

The next number with same set of digits is 92543

마무리

이 알고리즘은 자릿수 순회에 O(n), 정렬에 O(n log n)이 소요되므로 전체 시간 복잡도는 O(n log n)입니다. 이 방식은 C++ STL의 next_permutation 함수를 활용하는 방법으로도 대체할 수 있으며, 순열(permutation) 개념을 이해하는 데 매우 유용한 대표적인 문제입니다.