【JavaScript】スタックを使って小惑星の衝突後の最終状態を求めるアルゴリズム

問題の概要

1次元空間上に存在する複数の小惑星（アステロイド）の位置を表す配列 arr を受け取り、すべての衝突が完了した後の最終的な状態を返すJavaScript関数を作成します。

各要素において、絶対値は小惑星のサイズを、符号は移動方向を表します（正の値なら右方向、負の値なら左方向へ移動）。すべての小惑星は同じ速度で動くため、追いついて衝突するのは進行方向が逆向きのペアだけです。

衝突のルールは以下のとおりです。

• サイズが異なる場合：小さい方の小惑星のみが爆発して消滅します。
• サイズが同じ場合：両方の小惑星が爆発して消滅します。
• 同じ方向に移動している小惑星同士は、決して衝突しません。

入出力の例

入力

const arr = [7, 12, -8];

出力

const output = [7, 12];

解説

右へ進む「12」と左へ進む「-8」が衝突し、サイズの大きい「12」が残ります。「7」も右方向へ移動しているため、「12」と衝突することはありません。よって最終的な状態は [7, 12] となります。

解法コード

以下が実際のコードです。

const arr = [7, 12, -8];
const findState = (arr = []) => {
    const track = []
    for (const el of arr) {
        track.push(el)
        while (track[track.length - 1] < 0 && track[track.length - 2] > 0) {
            const a = -track.pop()
            const b = track.pop()
            if (a > b) {
                track.push(-a)
            } else if (a < b) {
                track.push(b)
            }
        }
    }
    return track
};
console.log(findState(arr));

出力結果

[7, 12]

コードの解説

このアルゴリズムのポイントはスタック（配列）を使ったシミュレーションです。処理の流れを順番に見ていきましょう。

1. 要素を順にスタックへ積む： 入力配列を先頭から1つずつ取り出し、track に追加していきます。
2. 衝突条件の判定： スタックの末尾2つを確認し、「左隣が正（右方向）・末尾が負（左方向）」という並びになっていたら、この2つは必ず衝突します。
3. 衝突処理： 2つの要素を pop() で取り出し、絶対値（サイズ）を比較します。
   ・負の側が大きければ -a を戻す
   ・正の側が大きければ b を戻す
   ・同サイズなら何も戻さず両方消滅させる
4. 衝突の連鎖： 新しく積まれた小惑星がさらに左側の小惑星と衝突する可能性があるため、衝突が起きなくなるまで while ループを継続します。

すべての要素を処理し終えたとき、スタックに残っている要素がそのまま最終的な生存小惑星の一覧になります。

計算量について

• 時間計算量：O(N) — 各小惑星は最大でも1回の追加と1回の取り出しだけ行われるため、全体として線形時間で処理できます。
• 空間計算量：O(N) — 最悪ケース（全員が同じ方向へ移動）では、すべての要素がスタックに保持されます。

単純に毎回配列全体を走査する方法よりも効率的で、競技プログラミングやコーディング面接でも頻出の「スタック活用パターン」の良い練習問題となっています。