技術とか戦略とか

IT技術者が技術や戦略について書くブログです。

例外ケースは処理の始めに除外する

プログラムで何かしらの処理を記述する場合、本当に実装したい処理(本処理)に入る前に、例外ケースを除外するテクニックがあります。
このように記述することで、本処理では例外ケースを考えずに済むため処理内容を考えやすくなりますし、例外ケースの場合に時間がかかる本処理を実行しなくて済むようになるので性能面でもメリットがあります。
 
例として、競技プログラミングの問題を取り上げて説明してみます。
 
今回取り上げる問題は以下です。
 100円玉がA枚、
 10円玉がB枚あります。
 X円を作る方法が何通りあるか出力しなさい。
 
ループ処理を実装して総当たりを行えばこの問題を解くことはできますが、その場合は性能面が犠牲になるため、望ましい解答ではありません。
今回は、ループ処理を使わずにこの問題を解いてみます。
(言語はJavaです。なお、本来は、標準入力を入力としますが、今回はソース中の定数を入力としています。)
 
----
 
【解答例】
・HundredYenTenYen.java
public class HundredYenTenYen {

    public static void main(String[] args){

        /* 問題
         * 100円玉がA枚、
         * 10円玉がB枚あります。
         * X円を作る方法が何通りあるか出力しなさい。
         * 入力: A B X
         */

        // 100円玉の枚数
        int A = 6; // 入力

        // 10円玉の枚数
        int B = 25; // 入力

        // 作りたい円
        int X = 550; // 入力

        System.out.println("入力:" + A + " " + B + " " + X);
        System.out.println("回答:" + execute(A, B, X));

    }

    public static int execute(int A, int B, int X) {

        // ①作りたい円が100円玉・10円玉の合計金額を超えていないか確認
        if ((A * 100) + (B * 10) < X) {
            return 0;
        }

        // ②作りたい円が10の倍数か確認
        if (X % 10 != 0) {
            return 0;
        }

        // ③持っている10円玉の枚数で、作りたい円の10の位を実現できるか確認
        if (B < (X % 100) / 10) {
            return 0;
        }

        // ④10円玉10枚の組はいくつあるか
        int BAfterPaidTensPlace = B - ((X % 100) / 10);
        int bulkOfTenTenYen = BAfterPaidTensPlace / 10;

        // ⑤100円玉だけの場合、作りたい円の100以降の位がどれくらい足りなくなるか
        int hundredsPlaceOfX = X / 100;
        int lackOfHundredYen = Math.max(hundredsPlaceOfX - A, 0);

        // ⑥10円玉で100円玉を代替するパターンがいくつあるか
        int patternOfReplacedHundredYenByTenYen
            = bulkOfTenTenYen - lackOfHundredYen;

        // ⑦総パターン数を返却
        return 1 + patternOfReplacedHundredYenByTenYen;

    }

}
 
【実行例】
・100円玉だけで100以降の位を払え、10の位を払った時に10円玉10枚組が減らない場合
入力:6 25 550
回答:3
 
 備考:以下の3パターンがある。
  100円玉5枚+10円玉5枚
  100円玉4枚+10円玉15枚
  100円玉3枚+10円玉25枚
 
・100円玉だけで100以降の位を払え、10の位を払った時に10円玉10枚組が減る場合
入力:6 25 460
回答:2
 
 備考:以下の2パターンがある。
  100円玉4枚+10円玉6枚
  100円玉3枚+10円玉16枚
 
・100円玉だけでは100以降の位を払えない場合
入力:6 25 840
回答:1
 
 備考:以下の1パターンがある。
  100円玉6枚+10円玉24枚
 
・持っている10円玉の枚数で、作りたい円の10の位を実現できない場合
入力:6 5 460
回答:0
 
・作りたい円が10の倍数ではない場合
入力:6 5 445
回答:0
 
・作りたい円が100円玉・10円玉の合計金額を超えている場合
入力:6 25 860
回答:0
 
----
 
この解答例では、「10円玉10枚の組み合わせは、100円玉1枚を代替できる」という点に着目し、④~⑦の箇所でパターン数を割り出しています。
 
そして、ポイントは、①~③で例外ケースを除外している所にあります。
①~③の例外処理を事前に噛ませることで、④~⑦に到達した時点で
・入力された金額は100円玉と10円玉で払い切れる
・入力された金額は必ず10の倍数である
・10の位を払う時に10円玉が足りなくなることはない
ということが保証されるため、④~⑦の処理を考えやすくなっています。
 
また、今回の例では当てはまりませんが、もし④~⑦が時間のかかる処理である場合は、例外ケースの場合に処理時間の短縮をすることもできます。
 
このように、例外ケースを事前に除外するテクニックが役に立つことがあるので、覚えておいて損はないでしょう。