Pythonでリストの両端から削除し、0と1のバランスを取るための最小削除回数を求めるプログラム

0と1のみが含まれるリストがあるとします。このリストに対して、先頭または末尾から値を削除できるものとします。最終的に、残ったリスト内の0と1の個数が等しくなるようにするには、最小で何回の削除が必要かを求めるのが目的です。

問題の例

たとえば、入力が nums = [1, 1, 1, 0, 0, 1] の場合を考えてみましょう。先頭の「1」と末尾の「1」を1つずつ削除すれば、残りは「1」が2個、「0」が2個となり、バランスが取れます。したがって、出力は 2 となります。

解法のアプローチ

この問題は、「累積和（prefix sum）」とハッシュマップを組み合わせたテクニックで効率的に解けます。考え方の手順は以下の通りです。

• 0 を「-1」、1 を「+1」とみなし、走査しながら累積和 currSum を更新していきます。
• 同じ累積和が2回現れた場合、その間の部分配列では 0 と 1 の個数が等しいことを意味します。
• 各累積和が最初に現れたインデックスをマップ d に記録し、再び同じ値が出たら、その差分から「バランスの取れた最長区間」の長さ longest を求めます。
• 最終的な答えは、「リスト全体の長さ − 最長のバランス区間の長さ」となります。

具体的なアルゴリズムは次の通りです。

• longest := 0 で初期化
• d := {0: -1} のマップを用意（キー0に初期値 -1 を設定）
• currSum := 0 で初期化
• i を 0 から nums のサイズまで繰り返す
  • nums[i] が 0 なら currSum -= 1、そうでなければ currSum += 1
  • currSum が d に存在すれば、longest = max(longest, i - d[currSum])
  • 存在しなければ d[currSum] := i を記録
• nums のサイズから longest を引いた値を返す

実装例

それでは、実際のPythonコードを見て理解を深めましょう。

class Solution:
    def solve(self, nums):
        longest = 0
        d = {0 : -1}
        currSum = 0
        for i in range(len(nums)):
            if nums[i] == 0:
                currSum -= 1
            else:
                currSum += 1
            if currSum in d:
                longest = max(longest, i - d[currSum])
            else:
                d[currSum] = i
        return len(nums) - longest

ob = Solution()
nums = [1, 1, 1, 0, 0, 1]
print(ob.solve(nums))

入力

[1, 1, 1, 0, 0, 1]

出力

2

計算量について

このアルゴリズムは、リストを一度だけ走査すればよいため、時間計算量は O(n)、ハッシュマップに各累積和を保存するため空間計算量も O(n) となります。全ての削除パターンを試す総当たり方式（O(n²)以上）に比べて大幅に効率的であり、大きなリストでも高速に動作します。