JavaScriptでn桁を削除して作れる最小の数を求める方法

問題

JavaScriptで、2つの引数を受け取る関数を書くことを考えます。第1引数を m、第2引数を n とします。

この関数の役割は、数値 m から n 桁を削除し、残った数字が表す数が最も小さくなるようにすることです。そして最後に、桁を削除した後の m を返します。

たとえば、次のような入力が与えられた場合を考えます。

const m = '45456757';
const n = 3;

このとき、期待される出力は次のとおりです。

const output = '44557';

出力の説明

「45456757」から「5」「6」「7」という3つの数字を取り除くことで、「44557」という最も小さい数を作ることができます。

コード例

この問題は、スタックを使った貪欲法（グリーディーアルゴリズム）で効率的に解くことができます。実装例は以下のとおりです。

const m = '45456757';
const n = 3;
const removeDigits = (m, n, stack = []) => {
    let arr = m.split('').map(Number);
    for(let el of arr){
        while (n && stack.length && el < stack[stack.length - 1]){
            stack.pop();
            --n;
        };
        stack.push(el);
    };
    let begin = stack.findIndex(el => el > 0);
    let end = stack.length - n;
    return (!stack.length || begin == -1 || begin == end) ? "0" : stack.slice(begin, end).join('').toString();
};
console.log(removeDigits(m, n));

コードの解説

ここでは、スタックを用いた貪欲法によって答えを構築しています。入力文字列 m の各桁 el を左から右へ順に走査し、スタックの先頭にある el より大きい値を最大 n 個まで取り除いたうえで、el をスタックにプッシュしていきます。

数値において左側の桁ほど重要度が高いため、この貪欲なアプローチにより、左側の桁には常にできるだけ小さい数字が配置されるようになります。その結果、スタックに残った大きな数字は右側の桁に集まることになります。

入力文字列 m の走査が終わった時点で、まだ削除すべき n 桁が残っている場合は、末尾から残り分を削除します。これは、右端の桁が比較的大きい数字になっているためです。

また、先頭のゼロを除去する処理や、すべての桁が削除された場合に「0」を返すフォールバック処理も組み込まれており、実用的なケースにも対応できます。

実行結果

コンソールには次のように出力されます。

44557