問題概要

整数で表される小惑星の配列 asteroids が与えられる。各小惑星について：

  • 絶対値：大きさ
  • 符号：方向（正=右、負=左）
  • 全て同じ速度で移動

衝突ルール：

  • 小さい方が爆発
  • 同じ大きさなら両方爆発
  • 同じ方向に移動する小惑星は衝突しない

全ての衝突後の状態を返せ。

失敗した実装

from collections import deque

class Solution:
    def asteroidCollision(self, asteroids: List[int]) -> List[int]:
        stack = []
        for aster in asteroids:
            if len(stack) <= 0 or (aster <= 0) == (stack[-1] <= 0):
                stack.append(aster)
            else:
                while len(stack) > 0 and (aster <= 0) != (stack[-1] <= 0) and abs(aster) > abs(stack[-1]):
                    stack.pop()
                if len(stack) <= 0 or (stack[-1] <= 0) == (aster <= 0):
                    stack.append(aster)
                elif abs(aster) == abs(stack[-1]):
                    stack.pop()
        return stack

問題点

  • 同じ条件判定 if len(stack) <= 0 or (stack[-1] <= 0) == (aster <= 0) が2箇所に重複
  • 制御フローが複雑で読みにくい
  • (aster <= 0) != (stack[-1] <= 0) は「符号が異なる」を検出するが、衝突しないケースも含む

最適解

class Solution:
    def asteroidCollision(self, asteroids: List[int]) -> List[int]:
        stack = []
        
        for asteroid in asteroids:
            while stack and asteroid < 0 < stack[-1]:
                # 右向き vs 左向きの衝突が発生
                if abs(stack[-1]) < abs(asteroid):
                    # 右向きが小さい → 爆発して次の右向きとも衝突判定
                    stack.pop()
                    continue
                elif abs(stack[-1]) == abs(asteroid):
                    # 同じ大きさ → 両方爆発
                    stack.pop()
                break
            else:
                # 衝突しなかった or 左向きが勝った
                stack.append(asteroid)
        
        return stack

わかったこと

1. ループ条件の本質

asteroid < 0 < stack[-1]

これは (asteroid < 0) and (0 < stack[-1]) と同じ。つまり：

  • asteroid が左向き（負）
  • stack[-1] が右向き（正）

2. パターンを表で整理すると明確になる

asteroid stack[-1] 条件 衝突する？ 理由
5 (右) 3 (右) False ❌ 同じ方向
-5 (左) -3 (左) False ❌ 同じ方向
5 (右) -3 (左) False ❌ 右が後ろから追いかける
-5 (左) 3 (右) True ✅ 正面衝突

衝突するパターンは1つだけ：左向きが右向きに突っ込む場合のみ。

3. while-elseの活用

Pythonの while-else 構文：

  • break で抜けた → else ブロックは実行されない
  • break せずループ終了 → else ブロックが実行される

この問題では：

  • break = 右向きが勝った or 引き分け → 新しい小惑星は追加しない
  • else = 衝突しなかった or 左向きが全て破壊 → 新しい小惑星を追加

4. 条件を絞り込む重要性

失敗実装では「符号が異なる」という広い条件を使い、後で追加判定が必要だった。

最適解では「衝突する唯一のケース」を直接表現することで、ロジックがシンプルになった。

学び

  • パターンを表で整理すると、本質的な条件が見える
  • ループ条件は狭く絞るほど、内部ロジックがシンプルになる
  • while-else は状態管理をエレガントに表現できる

計算量

  • 時間計算量：O(n) - 各小惑星は最大1回スタックに追加され、1回削除される
  • 空間計算量：O(n) - 最悪の場合、全ての小惑星がスタックに残る