【C++】同じ数字の組み合わせで作れる「Nより小さい最大の数」を求めるアルゴリズム

問題の概要

この問題では、ある数値を表す文字列 N が与えられます。求めるのは、N を構成するすべての桁の数字を使い、なおかつ N より小さくなる数のうち最大のものです。

入出力の例

• 入力: N = "54314"
• 出力: 54143

「54314」の各桁(5, 4, 3, 1, 4)を並べ替えて作れる数のうち、54314 未満で最大なのは「54143」です。

解法のアプローチ

この問題の基本的な考え方は、「どの桁を入れ替えれば N より小さい最大の数になるか」を見つけることです。ここで重要なのは、ある桁がその左隣の桁より小さい場合、その位置で並べ替えを行うと必ず元の数より小さい数が作れるという性質を利用する点です。

具体的な手順は以下の通りです。

1. 数値を右から左へ走査し、N[i] < N[i-1](自分の左隣の桁より小さい)となる最初の位置 i を見つけます。
2. そのような位置が存在しない場合(数字が左から昇順に並んでいる場合)、それより小さい数は作れないため処理を終了します。
3. i 以降の部分から、N[i-1] より小さい数字のうち最大のものを探します。
4. 見つけた数字と N[i-1] を交換します。
5. 最後に、i 以降の部分を降順にソートします。これで答えが完成します。

先頭から i-2 までの桁は元のままなので、i-1 の桁が小さくなった時点で数全体は確実に N より小さくなります。したがって、残りの桁を降順に並べることで、N 未満という制約の中で数を最大化できるのです。

C++での実装例

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

void calcGreatestSmallerElement(string N, int size) {

    int i, j;
    // 右から左へ走査し、左隣より小さい桁を探す
    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;
    // N[i-1] より小さい数字のうち最大のものを探す
    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(d)(d は桁数)、降順ソートが O(d log d) で行えるため、全体の計算量は O(d log d) となります。「次に大きい数(Next Permutation)」を求める有名な問題の逆バージョンにあたり、桁の大小関係に着目した効率的な解法を学べる良い例題です。