【ITニュース解説】Day 3 of 100 days dsa coding challenge

「100日間DSAコーディングチャレンジ」という取り組みは、システムエンジニアを目指す皆さんにとって、非常に価値ある学習方法の一つだ。DSAとは「データ構造とアルゴリズム」の略で、効率的なプログラムを書くために不可欠な知識である。このチャレンジでは、毎日一つずつアルゴリズムの問題を解くことで、実践的な問題解決能力とコーディングスキルを向上させることを目的としている。GeeksforGeeksのようなプラットフォームで毎日出題される「今日の問題（POTD）」に取り組むことは、知識の定着と応用力育成に繋がる。

今回取り上げられた問題は「Expression Add Operators」というもので、難易度が「ハード」に設定されている。この問題は、与えられた数字のみで構成される文字列sと、目標となる整数targetに対し、sの数字の間に二項演算子+、-、*を挿入することで、結果としてtargetになるようなすべての有効な式を文字列として返すことを求める。例えば、文字列"124"と目標値9が与えられた場合、"1+2*4"という式が答えとなる。この式は1 + (2 * 4) = 1 + 8 = 9と計算され、目標値に一致する。

問題にはいくつかの重要なルールがある。一つ目は、生成される数値（オペランド）には先行ゼロを含めることはできないという点だ。例えば、"2 + 03"のような式は無効だが、"20 + 3"のように20という数値自体が有効な場合は問題ない。これは、数値の解釈を明確にするためのルールである。二つ目は、数字の間に必ずしも演算子を挿入する必要はないという点だ。例えば、"12"という文字列が与えられ、目標値が12の場合、そのまま"12"という式が有効な解となる。三つ目は、最終的な結果のリストは、辞書順（アルファベット順）でソートされて返されることだ。入力文字列sの長さは1文字から9文字まで、sは0から9の数字のみで構成される。目標値targetは、一般的な整数型で表現できる範囲内の値である。

この問題の難易度が「ハード」であり、正答率が61.49%であることは、多くの人が挑戦しても簡単には解けないことを示している。しかし、このような複雑な問題に挑戦し、解決策を理解することは、論理的思考力とアルゴリズム設計能力を飛躍的に向上させる。これは、システムエンジニアとして多岐にわたる問題解決に取り組む上で、非常に重要な基礎となる力だ。

この問題の解決には、「バックトラック」と呼ばれるアルゴリズムが使われている。バックトラックは、全ての可能性を網羅的に探索するアルゴリズムの一種で、ある状態から次の状態へと進み、もしその道筋が解に繋がらないと判断したら、前の状態に戻って別の道筋を試す、という方法だ。まるで迷路を解くように、行き止まりに出会ったら引き返す、とイメージすると分かりやすいだろう。

提供されているPythonのコードでは、SolutionクラスのfindExprメソッドがメインの処理を担当し、内部でbacktrackという再帰関数を呼び出している。再帰関数とは、自分自身を呼び出すことで繰り返し処理を行う関数のことだ。

backtrack関数は、以下の4つの引数を受け取る。

• index: 現在、文字列sのどの位置の数字を処理しているかを示すインデックス。
• expr: 現在構築中の式を表す文字列（例: "1+2"）。
• value: 現在構築中の式を評価したときの数値結果（例: 1+2=3）。
• last: 直前に加算または減算された数値、あるいは乗算に使用された最後の数値。これは、乗算の優先順位を正しく処理するために非常に重要となる。

backtrack関数の処理の流れを見てみよう。 まず、終了条件として、indexが文字列sの長さに等しくなった場合、つまりsの全ての数字を使い切ったときに、現在のvalueがtargetと一致していれば、現在の式exprは有効な解なので、結果リストresに追加する。その後、このパスの探索を終了する。

次に、indexからsの終わりまで、ループを使って可能な全ての数値の区切り方を試す。例えば、s = "124"でindex = 0の場合、まず"1"を数値として扱う、次に"12"を数値として扱う、そして"124"を数値として扱う、というように、indexから始まる全ての部分文字列を数値numとして試す。ここで重要なのは、先行ゼロのチェックだ。i != indexかつs[index] == '0'という条件は、例えば"03"のような0で始まる数値が生成されないようにするためのチェックだ。単独の"0"は有効だが、"01", "00"などは無効となる。この条件に合致すれば、それ以降の部分文字列も先行ゼロを持つことになるため、ループを中断する。有効な部分文字列が見つかれば、それを整数numに変換する。

そして、演算子の挿入と再帰呼び出しを行う。

• 最初の数値の場合 (index == 0): 式の最初の数値なので、演算子を挿入せず、numをそのまま現在の値valueおよびlastとしてbacktrackを再帰的に呼び出す。exprはstr(num)となる。
• 2番目以降の数値の場合: +、-、*の3種類の演算子をそれぞれ試す。
  • +演算子: exprの文字列に'+'とnumを連結した新しい式を生成し、valueにnumを加算したものを新しいvalueとし、numを新しいlastとしてbacktrackを呼び出す。
  • -演算子: exprの文字列に'-'とnumを連結した新しい式を生成し、valueからnumを減算したものを新しいvalueとし、-numを新しいlastとしてbacktrackを呼び出す。lastを-numとするのは、後続の乗算で正しく演算を行うためだ。
  • *演算子: この処理が最も複雑だ。乗算は加算・減算よりも優先されるため、直前の演算の影響を取り消す必要がある。現在のvalueから直前のlastの値を引いて、last * numを計算し、その結果を足し合わせる。つまり、value - last + last * numが新しいvalueとなる。新しいlastはlast * numとなる。この仕組みにより、1+2*4のような式が1 + (2*4)と正しく評価される。

全ての探索が終わると、findExprメソッドは結果リストresを辞書順にソートして返す。

この「Expression Add Operators」問題は、単に計算するだけでなく、バックトラックという強力なアルゴリズムを駆使し、演算子の優先順位や先行ゼロといった細かいルールにも対応する必要がある、非常に奥深い問題だ。このような問題に挑戦し、その解決策をコードレベルで理解することは、複雑なロジックを設計し、実装する能力を養う上で不可欠な経験となる。システムエンジニアにとって、効率的で正確なプログラムを作成するために、このようなアルゴリズムの知識と問題解決の経験は、必ず役立つ基礎力となるだろう。日々のコーディングチャレンジを通じて、着実にスキルを向上させてほしい。