C++でY以下となる数値集合の最小個数を求めるアルゴリズム

問題の概要

連続した数字からなる文字列と数値 Y が与えられます。このとき、以下のルールをすべて満たす集合の最小個数を求めるのが課題です。

• 各集合は、元の文字列から連続して取り出した数字で構成すること
• 同じ桁（文字）を複数回使用してはならない
• 集合内の数値は Y を超えてはならない

入力例と出力例

たとえば、str = "1234"、Y = 20 とすると、次のように 3 つの集合に分割できるため、答えは 3 になります。

{12}, {3}, {4}

{12} は 20 以下であり、{3} と {4} もそれぞれ 20 以下です。すべての数字が一度ずつ使われていることも確認できます。

アルゴリズム

この問題は貪欲法（グリーディ法）で解くことができます。文字列を左から順に走査し、可能な限り長い数値を現在の集合に追加していく方針です。

• 文字列を左から走査し、現在の数値 num を num = num * 10 + (現在の桁の値) として更新する
• num が Y 以下であれば、フラグ f を 1 に設定する（現在の集合は有効）
• num が Y を超えた場合、f が 1 ならカウントを 1 増やし、f を 0 にリセットする。そのうえで、num を現在の桁の値（s[i]-'0'）で再初期化する。現在の桁が単独でも Y を超える場合は、num を 0 にする
• 文字列全体の走査が終わった後、f が 1 であればカウントを 1 増やす（最後の集合を数える）

C++での実装例

#include <iostream>
#include <string>
using namespace std;
int getMinSets(string str, int y) {
    int cnt = 0;
    int num = 0;
    int l = str.length();
    int f = 0;
    for (int i = 0; i < l; ++i) {
        num = num * 10 + str[i] - 48;
        if (num <= y) {
            f = 1;
            continue;
        }
        if (f) {
            ++cnt;
        }
        num = str[i] - '0';
        f = 0;
        if (num <= y) {
            f = 1;
        } else {
            num = 0;
        }
    }
    if (f) {
        ++cnt;
    }
    return cnt;
}
int main() {
    string str = "1234";
    int y = 20;
    cout << "Minimum sets = " << getMinSets(str, y) << endl;
    return 0;
}

出力結果

上記のプログラムをコンパイルして実行すると、次の出力が得られます。

Minimum sets = 3

計算量

文字列を一度だけ走査するため、時間計算量は O(n)（n は文字列の長さ）、空間計算量は O(1) です。数値が Y を超えた時点で集合を確定して次の桁から再スタートするシンプルな貪欲戦略により、効率的に最小個数を求められます。