【ITニュース解説】🗓 Daily LeetCode Progress – Day 17

プログラミングの世界には、効率的に問題を解決する能力が求められる。システムエンジニアを目指す上で、そうした能力を磨くためのツールの一つが「LeetCode」というオンラインプラットフォームだ。ここでは、さまざまなプログラミングの課題が出題され、それを解くことでアルゴリズムやデータ構造の理解を深めることができる。今回紹介する記事は、まさにそのLeetCodeでの日々の学習記録、「デイリーLeetCodeプログレス」の17日目にあたる。

この記事では、特に「配列（Array）」というデータの並びを扱う二つの問題に焦点を当てて解説されている。配列は、同じ種類のデータを順番に並べて格納する基本的なデータ構造で、プログラミングでは頻繁に利用される。取り上げられた問題は「Minimum Operations to Exceed Threshold Value I」と「Move Zeroes」だ。

まず、「Minimum Operations to Exceed Threshold Value I」という問題を見てみよう。この問題は、整数が格納された配列と、ある「閾値k」が与えられたときに、配列の中から「現在の最小の要素」を取り除くという操作を繰り返して、残った全ての要素が閾値k以上になるまでに何回操作が必要か、を問うものだ。例えば、[10, 4, 7, 2]という配列と閾値k=5があったとしよう。最初は2が最小なので2を取り除く。次に4が最小なので4を取り除く。この時点で配列は[10, 7]となり、全ての要素が5以上になった。操作は2回必要だった、という具合だ。

この記事の著者はこの問題を解く上で重要な洞察を得ている。それは、「最小の要素を取り除く」という操作は、結局のところ、閾値kよりも小さい全ての要素を一つずつ取り除かなければならない、という点だ。なぜなら、閾値k未満の要素が一つでも残っている限り、その要素がいつか「最小の要素」として選ばれて取り除かれることになるからだ。したがって、この問題の答えは、単純に配列の中に閾値kよりも小さい要素がいくつあるかを数えるだけで良い、ということになる。

解決策としては、まず配列を小さい順に「ソート（並べ替え）」する方法が示されている。ソートすることで、閾値kよりも小さい要素は配列の先頭に集まる。あとは配列の先頭から順に要素を見ていき、k未満である限りカウントアップしていけば、必要な操作回数がわかる。C++やPythonのコードでは、sort関数を使って配列をソートした後、whileループを使って先頭から要素をチェックし、k未満の要素の数を数えている。このアプローチは非常に直感的で理解しやすいだろう。

この解法の効率性について考えよう。効率性を示す指標として「時間計算量」と「空間計算量」がある。時間計算量は、アルゴリズムが完了するまでにかかる時間の指標で、入力データのサイズ（ここでは配列の要素数n）が大きくなったときに時間がどれくらい増えるかを示す。空間計算量は、アルゴリズムが実行中に使用するメモリ量の指標だ。 「Minimum Operations to Exceed Threshold Value I」におけるソートを使った解法では、時間計算量は「O(n log n)」となる。これは、多くのソートアルゴリズムがこの程度の時間で動作するためだ。nが大きくなると、nにlog nを掛けた分だけ処理時間が増えることを意味する。配列をソートせずに直接数える方法もあるが、ソートを含まない場合はO(n)となり、より効率が良い場合もある。しかし、この問題の解決策としてはどちらも正しい。空間計算量は「O(1)」とされている。これは、追加のメモリをほとんど使わずに、元の配列を直接操作して問題を解く「インプレース（in-place）」な解法であることを意味する。つまり、入力データのサイズに関わらず、ごくわずかな追加メモリしか使用しないということだ。

次に、「Move Zeroes」という問題だ。これは、整数が格納された配列が与えられたときに、配列内の全ての「ゼロ」を配列の末尾に移動させ、それ以外の非ゼロの要素の相対的な順序は変えない、という問題だ。例えば、[0, 1, 0, 3, 12]という配列があれば、結果は[1, 3, 12, 0, 0]となる。1, 3, 12という非ゼロの要素の順序は保たれている点に注目してほしい。

この記事の著者は、この問題を「インプレースで要素を削除（erase/pop）し、末尾に追加（push_back/append）する」という方法で解決している。具体的には、配列の先頭から順に要素をチェックし、もしゼロが見つかったら、そのゼロを現在の位置から削除し、すぐに配列の末尾に追加し直す。この操作を繰り返すことで、全てのゼロが配列の末尾に移動し、非ゼロの要素の相対的な順序も保たれる。C++のコードではeraseとpush_back、Pythonのコードではpopとappendという関数が使われている。

この解法は意図通りに動作するが、その効率性には注意が必要だ。このアプローチの時間計算量は「O(n^2)」となる。なぜなら、配列の途中から要素を削除する操作（eraseやpop）は、その要素より後ろにある全ての要素を一つずつ前にずらす必要があるため、O(n)の時間がかかるからだ。これが配列の長さ（n）回繰り返される可能性があるため、全体としてO(n) × O(n) = O(n^2)という計算量になってしまう。nが大きくなると、この処理時間は非常に大きく増加してしまうため、あまり効率が良いとは言えない。空間計算量は「O(1)」で、こちらもインプレースな操作のため、追加のメモリ使用はほとんどない。

記事の注記には、より効率的な「二つのポインタ（two-pointer）」を使うO(n)の解法が存在することも書かれている。これは、ゼロでない要素を配列の先頭から順に詰めていき、残った部分をゼロで埋めるという方法だ。今回の著者の解法は、配列の途中の要素を削除・追加する操作の特性を理解する良い例になっている。

今回の学習から得られる教訓は二つある。一つは、問題文の操作（「最小値の削除」）が、実はより単純な操作（「閾値未満の要素のカウント」）と等しいという「不変条件」を見抜くことの重要性だ。もう一つは、アルゴリズムの効率性、特に時間計算量を意識することの重要性だ。同じ問題でも、どのようなアプローチを取るかによって、プログラムの実行速度が大きく変わることがある。システムエンジニアにとって、与えられた問題を正しく解くだけでなく、その解法がどれだけ効率的であるかを評価する能力も非常に重要となる。

これらの日々の学習を通じて、アルゴリズムやデータ構造に関する知識を深め、より良いプログラミングスキルを身につけることができる。このような継続的な取り組みは、システムエンジニアとしての成長に不可欠なものとなるだろう。