C++로 동일한 자릿수를 사용해 N보다 작은 가장 큰 수 찾기

이 문제에서는 하나의 숫자를 나타내는 문자열 N이 주어집니다. 우리의 목표는 N을 구성하는 자릿수를 모두 그대로 사용하면서 N보다 작은 수 중 가장 큰 수를 찾는 것입니다.

문제 설명

주어진 숫자의 자릿수 집합은 유지한 채 자릿수의 순서만 재배열하여, 원래 수보다 작으면서 가능한 한 큰 수를 만들어야 합니다. 순열 관점에서 보면 이는 해당 숫자의 '바로 이전 순열(previous permutation)'을 구하는 문제와 같습니다.

예시로 이해하기

입력: N = "54341"
출력: 54314

자릿수 {5, 4, 3, 4, 1}로 만들 수 있는 숫자 중 54341보다 작은 수는 여러 개 있지만, 그중 가장 큰 값은 54314입니다.

해결 접근 방법

핵심 아이디어는 다음과 같습니다. 전체 수를 작게 만들려면 어느 한 자릿수를 더 작은 값으로 바꿔야 하고, 결과를 최대한 크게 유지하려면 가능한 한 오른쪽에 있는 자릿수를 교체 대상으로 삼아야 합니다. 따라서 숫자를 오른쪽에서 왼쪽으로 훑으며 '자신의 오른쪽 이웃보다 큰' 첫 번째 자릿수를 찾습니다.

오른쪽에서 왼쪽으로 탐색하며 N[i] < N[i-1]을 만족하는 첫 번째 위치 i를 찾습니다. 이때 N[i-1]이 교체할 자릿수입니다.
그러한 위치가 없다면(i == 0) 자릿수가 이미 오름차순으로 정렬되어 있다는 뜻이므로, 더 작은 순열은 존재하지 않습니다.
x = N[i-1]로 놓고, i번째부터 끝까지의 부분 배열에서 x보다 작으면서 가장 큰 값을 찾아 그 인덱스를 greatest에 저장합니다.
N[greatest]와 N[i-1]을 서로 교환(swap)합니다.
i부터 끝까지의 부분 문자열을 내림차순으로 정렬합니다. 남은 자릿수를 큰 값부터 배치해야 전체 결과가 최대한 커지기 때문입니다.
완성된 문자열이 곧 정답입니다.

구현 예제

#include <bits/stdc++.h>
using namespace std;

// 동일한 자릿수로 만들 수 있는 N보다 작은 가장 큰 수를 계산하는 함수
void calcGreatestSmallerElement(string N, int size) {
    int i, j;

    // 오른쪽에서 왼쪽으로 탐색하며 N[i] < N[i-1]인 지점을 찾음
    for (i = size - 1; i > 0; i--)
        if (N[i] < N[i - 1])
            break;

    // 자릿수가 오름차순이면 더 작은 순열이 존재하지 않음
    if (i == 0) {
        cout << "Previous number is not possible";
        return;
    }

    int x = N[i - 1], greatest = i;

    // 오른쪽 부분에서 x보다 작으면서 가장 큰 자릿수를 찾음
    for (j = i; j < size; j++)
        if (N[j] < x && N[j] > N[greatest])
            greatest = j;

    // 두 자릿수를 교환
    swap(N[greatest], N[i - 1]);

    // 남은 부분을 내림차순으로 정렬해 결과를 최대화
    sort(N.begin() + i, N.begin() + size, greater<char>());

    cout << "The Greatest smaller number with same set of digits is " << N;

    return;
}

int main() {
    string N = "654232";
    int size = N.length();
    cout << "The number is " << N << endl;
    calcGreatestSmallerElement(N, size);

    return 0;
}

출력

The number is 654232
The Greatest smaller number with same set of digits is 654223

복잡도 분석

탐색과 교환에는 O(n)의 시간이, 내림차순 정렬에는 O(n log n)의 시간이 소요되므로 전체 시간 복잡도는 O(n log n)입니다. 입력 문자열을 제자리에서 수정하므로 추가 공간 복잡도는 O(1)입니다.

마무리

이 알고리즘은 '이전 순열 생성' 기법을 숫자 문자열에 적용한 것으로, 자릿수를 재배열해 사전적으로 바로 앞선 수를 효율적으로 구할 수 있습니다. 교체 기준점을 오른쪽에서 찾고, 남은 자릿수를 내림차순으로 배치하는 두 단계가 결과를 최적화하는 핵심입니다.