C++で解く小惑星の衝突問題:スタックを活用した効率的なアプローチ

問題の概要

整数の配列 asteroids が与えられ、一列に並んだ小惑星を表しているとします。各小惑星において、絶対値はそのサイズを、符号は移動方向を表します(正の値は右方向、負の値は左方向)。すべての小惑星は同じ速度で移動します。

この問題の目的は、すべての衝突が発生し終わった後の小惑星の状態を求めることです。2つの小惑星が出会うと、サイズが小さい方が爆発します。サイズが同じ場合は両方が爆発します。また、同じ方向に移動している2つの小惑星は、速度が等しいため決して出会うことはありません。

例えば、入力が [5, 10, -5] の場合、出力は [5, 10] になります。これは、10 と -5 が衝突して -5 が爆発し、その後 5 と 10 は同じ方向へ進むため衝突しないからです。

解法のアプローチ

この問題は、スタックのような働きをする配列を使うことで効率的に解けます。小惑星を左から順に処理し、衝突が発生する条件(スタックの末尾の小惑星が右方向=正の値で、現在の小惑星が左方向=負の値)に該当する場合のみ、衝突処理を行います。

アルゴリズムの手順

• 結果を格納する配列 ret を用意し、n を配列 arr のサイズとします。

• i が 0 から n-1 までの間、以下を繰り返します。

  • ret が空、または衝突が発生しない場合(ret の末尾要素が負、もしくは arr[i] が正):arr[i] を ret に追加し、i を1増やします。

  • それ以外(衝突が発生する場合):

    • x を ret の末尾要素とし、末尾を削除します。

    • absX = |x|、absY = |arr[i]| とします。

    • absX == absY の場合:両方が爆発するため、i を1増やします。

    • absX > absY の場合:x を ret に戻し、i を1増やします。

    • absX < absY の場合:x だけが爆発し、i はそのまま。次のループで継続して比較します。

• 最後に ret を返します。

C++での実装例

以下の実装を見ると、より理解が深まるでしょう。

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
        cout << v[i] << ", ";
    }
    cout << "]"<<endl;
}
class Solution {
    public:
    bool isNeg(int x){
        return x < 0;
    }
    vector<int> asteroidCollision(vector<int>& arr) {
        vector <int> ret;
        int n = arr.size();
        for(int i = 0; i< n; ){
            if(ret.empty() || !(!isNeg(ret[ret.size() - 1]) && isNeg(arr[i]))){
                ret.push_back(arr[i]);
                i++;
            } else {
                int x = ret[ret.size() - 1];
                ret.pop_back();
                int absX = abs(x);
                int absY = abs(arr[i]);
                if(absX == absY){
                    i++;
                } else {
                    if(absX > absY){
                        ret.push_back(x);
                        i++;
                    }
                }
            }
        }
        return ret;
    }
};
main(){
    vector<int> v = {5, 10, -4};
    Solution ob;
    print_vector(ob.asteroidCollision(v));
}

入力

[5,10,-4]

出力

[5, 10]

計算量の分析

このアルゴリズムの時間計算量は O(n) です。各小惑星は最大でも2回(追加時と衝突処理時)しか処理されないためです。空間計算量も O(n) で、結果を格納する配列 ret が最悪ケースですべての小惑星を保持する可能性があるためです。