C++で数値が「1」「14」「144」の連結のみで構成されているか判定する方法

本記事では、与えられた数値や文字列が「1」「14」「144」のみを連結した形になっているかどうかを判定する問題を解説します。例えば、文字列「111411441」はこれらの数字の組み合わせで表現できるため有効ですが、「144414」はどの組み合わせでも表現できないため無効となります。

アルゴリズムの考え方

判定方法は非常にシンプルです。以下の手順で処理を行います。

まず、数値の末尾から1桁・2桁・3桁ずつ数字を取り出し、それが「1」「14」「144」のいずれかに一致するかを確認します。

一致するパターンが見つかったら、その桁数に対応する数（10・100・1000）で数値を割り、残りの部分に対して同じ処理を繰り返します。この操作を数値が完全になくなるまで続け、最後まで問題なく分解できれば、その数値は有効であると判断できます。

C++による実装例

#include <iostream>
#include <cmath>
using namespace std;
bool checkNumber(long long number) {
   int n = number;
   while (n > 0) {
      if (n % 1000 == 144)
         n /= 1000;
         else if (n % 100 == 14)
            n /= 100;
         else if (n % 10 == 1)
            n /= 10;
      else {
         return false;
      }
   }
   return true;
}
int main() {
   long long n = 111411441;
   if(checkNumber(n)){
      cout << "Valid number";
   } else {
      cout << "Invalid number";
   }
}

実行結果

Valid number

コードのポイント

この実装では、剰余演算（%）を使って末尾の桁を効率的に取り出しています。「144」→「14」→「1」の順に優先的にチェックすることで、より長いパターンから先にマッチさせ、誤った分解を防いでいる点が重要です。計算量は数値の桁数に比例するため、非常に効率的なアルゴリズムとなっています。