JavaScriptで全ての客に正確な釣り銭を渡せるかどうかを判定する方法

問題

数値の配列 arr を唯一の引数として受け取るJavaScript関数を作成する必要があります。

次のような状況を想定してみましょう。

ある店主が、価格がちょうど₹5(5ルピー)の商品を販売しています。店の前には複数の客が列になって並んでおり、それぞれがこの商品を1つずつ購入します。客が支払えるのは₹5、₹10、₹20のいずれかの紙幣です。店主は最初は1枚も現金を持っておらず、配列には列に並んだ順番に各客が支払う紙幣が記録されています。

このとき、店主はすべての客に対して正確な釣り銭を渡せるでしょうか。それを判定するのが今回作成する関数の役割です。

例えば、関数への入力が次の場合を考えます。

入力

const arr = [5, 5, 10, 10, 20];

出力

const output = false;

出力の説明

最初に受け取った2枚の₹5紙幣は、₹10紙幣で支払った2人分のお釣り(各₹5)として使ってしまいます。その結果、最後に₹20紙幣で支払われた際に必要な₹15の釣り銭を用意することができません。したがって答えは false となります。

以下が実際のコードです。

コード例

const arr = [5, 5, 10, 10, 20];
const provideChanges = (arr = []) => {
    let fives = 0
    let tens = 0
    for(let i = 0; i < arr.length; i++) {
        switch(arr[i]) {
            case 5:
                fives += 1
                break
            case 10:
                if(fives <= 0) {
                    return false
                }
                fives -= 1
                tens += 1
                break
            default:
                if(tens >= 1 && fives >= 1) {
                    tens -= 1
                    fives -= 1
                } else if(fives >= 3) {
                    fives -= 3
                } else {
                    return false
                }
                break
        }
    }
    return true
};
console.log(provideChanges(arr));

コードの解説

このアルゴリズムのポイントは、店主の手元にある紙幣の枚数を常に把握しておくことです。貪欲法(greedy)の考え方に基づいて、客を一人ずつ処理していきます。

• ₹5を受け取った場合: 釣り銭は不要なので、変数 fives を1増やすだけです。
• ₹10を受け取った場合: ₹5を1枚返す必要があります。手元に₹5がなければ即座に false を返します。釣り銭を渡せた場合は fives を1減らし、代わりに tens を1増やします。
• ₹20を受け取った場合: 合計₹15のお釣りが必要です。優先的に「₹10×1枚 + ₹5×1枚」の組み合わせで渡します。それが不可能なら「₹5×3枚」で対応し、どちらもできなければ false を返します。

特に重要なのは、₹20の釣り銭では₹10紙幣を優先して使う点です。₹5紙幣の方が汎用性が高く、後の客への対応にも使い回せるため、できるだけ手元に残しておくのが賢明だからです。

配列を先頭から一度だけ走査すればよいため、時間計算量はO(n)、空間計算量もO(1)と非常に効率的です。

出力

false