C++의 소행성 충돌

행에 소행성을 나타내는 정수 배열이 있다고 가정합니다. 이제 각 소행성에 대해 절대값은 크기를 나타내고 부호는 각각 오른쪽과 왼쪽에 대해 양수 또는 음수일 수 있는 방향을 나타냅니다. 각 소행성은 같은 속도로 움직입니다.

우리는 모든 충돌 후에 소행성의 상태를 찾아야 합니다. 두 개의 소행성이 만나면 작은 소행성이 폭발합니다. 둘 다 크기가 같으면 둘 다 폭발합니다. 같은 방향으로 움직이는 두 개의 소행성은 결코 만나지 않을 것입니다.

따라서 입력이 [5, 10, -5]와 같으면 출력은 [5, 10]이 됩니다. 여기서 10과 -5는 10에서 충돌하고 5와 10은 절대 충돌하지 않습니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 하나의 배열을 ret, n :=arr의 크기

  로 만듭니다.

• 0 ~ n – 1 범위의 i에 대해

  • ret가 비어 있거나 ret의 마지막 요소가 양수이고 arr[i]가 음수이면

    • arr[i]를 ret에 삽입하고 i를 1만큼 증가

  • 그렇지 않으면

    • x :=ret의 마지막 요소, ret에서 마지막 요소 삭제

    • absX :=|x|, absY :=|arr[i]|

    • absX =absY이면 i를 1만큼 증가

    • 그렇지 않으면

      • absX> absY이면 x를 ret에 삽입하고 i를 1만큼 증가

• 리턴 렛

예시(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, ]