Pythonで解く！ロケット同士の衝突後の最終状態を求めるアルゴリズム

問題の概要

数値のリスト nums が与えられ、それぞれの要素はロケットの「向き」と「大きさ」を表しているとします。正の整数は右方向への移動、負の数は左方向への移動を意味し、数値の絶対値がロケットの大きさを表します。

2つのロケットが衝突したときのルールは以下の通りです。

• 大きさが異なる場合：小さい方のロケットが破壊され、大きい方のロケットはそのまま進み続けます
• 大きさが同じ場合：2つのロケットは互いに破壊し合います
• 同じ方向に移動している場合：速度が同じであるため、衝突することはありません

このとき、すべての衝突が完了した後のロケットの状態を求めるのが本記事のテーマです。

たとえば、入力が nums = [3, 8, 5, -5] の場合、出力は [3, 8] になります。これは、5 と -5 が衝突して互いに破壊し合い、残りのロケットが生き残るためです。

解法のアプローチ

この問題は、リストをスタックのように扱うことで効率よく解くことができます。具体的な手順は次の通りです。

1. ls を、nums[0] の1要素だけを持つ新しいリストとして初期化します
2. i を 1 から nums の長さ - 1 まで順に処理します。
   • nums[i] >= 0（右方向）の場合：nums[i] を ls の末尾に追加するだけです
   • nums[i] が負の数（左方向）の場合：nums[i] を ls の末尾に追加したうえで、左側にいる右方向のロケットとの衝突判定を行います。j を「ls の長さ - 2」とし、「j >= 0 かつ ls[j] >= 0」の間、以下を繰り返します。
     • |ls の末尾要素| > ls[j] の場合：ls[j] を削除します（左方向のロケットが勝ち、さらに左のロケットとも衝突判定を続けます）
     • |ls の末尾要素| == ls[j] の場合：両方の要素を削除してループを抜けます
     • それ以外の場合：ls の末尾要素を削除してループを抜けます（右方向のロケットの方が大きいため）
   • 条件分岐の後、j を 1 減らします
3. 最終的に ls を返します

実装例

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

class Solution:
    def solve(self, nums):
        ls = [nums[0]]
        for i in range(1, len(nums)):
            if nums[i] >= 0:
                ls.append(nums[i])
            else:
                ls.append(nums[i])
                j = len(ls) - 2
                while j >= 0 and ls[j] >= 0:
                    if abs(ls[-1]) > ls[j]:
                        ls.pop(j)
                    elif abs(ls[-1]) == ls[j]:
                        ls.pop(j)
                        ls.pop(-1)
                        break
                    else:
                        ls.pop(-1)
                        break
                    j -= 1
        return ls

ob = Solution()
nums = [3, 8, 5, -5]
print(ob.solve(nums))

入力

[3, 8, 5, -5]

出力

[3, 8]

動作の流れを追ってみよう

入力 [3, 8, 5, -5] の場合、処理は次のように進みます。

1. 初期状態：ls = [3]
2. 8 は正の数なのでそのまま追加 → ls = [3, 8]
3. 5 も正の数なのでそのまま追加 → ls = [3, 8, 5]
4. -5 は負の数なので追加し、衝突判定へ → ls = [3, 8, 5, -5]
   • |-5| = 5 と直前の 5 を比較すると等しいため、両方を削除 → ls = [3, 8]
5. すべての処理が完了し、[3, 8] が返されます

計算量について

各ロケットは最大で1回ずつ追加・削除されるため、全体の時間計算量は O(n) となります。また、結果を保持するためのリストが必要なため、空間計算量も O(n) です。