문제 개요
정수 배열 asteroids에는 일렬로 나열된 소행성들이 담겨 있습니다. 각 원소에서 절댓값은 소행성의 크기를, 부호는 이동 방향을 나타냅니다. 양수는 오른쪽으로, 음수는 왼쪽으로 이동하며, 모든 소행성은 동일한 속도로 움직입니다.
우리가 구해야 할 것은 모든 충돌이 끝난 후 소행성들의 최종 상태입니다. 충돌 규칙은 다음과 같습니다.
- 두 소행성이 만나면 크기가 작은 쪽이 폭발합니다.
- 크기가 같다면 두 소행성 모두 폭발합니다.
- 같은 방향으로 움직이는 소행성은 절대 만나지 않습니다.
예를 들어 입력이 [5, 10, -5]라면 출력은 [5, 10]입니다. 10과 -5가 충돌하여 -5가 사라지고, 5와 10은 같은 방향으로 움직이기 때문에 서로 충돌하지 않습니다.
접근 방법: 스택(Stack) 활용
이 문제는 스택을 사용하면 효율적으로 해결할 수 있습니다. 소행성을 하나씩 처리하면서, 충돌이 가능한 경우(스택의 top이 오른쪽으로 이동하는 양수이고, 현재 소행성이 왼쪽으로 이동하는 음수인 경우)에만 크기를 비교합니다.
알고리즘 단계
- 결과를 저장할 배열
ret을 선언하고,n을 입력 배열의 크기로 설정합니다. i가 0부터 n-1까지일 동안 반복합니다.ret이 비어 있거나, 충돌 조건(top이 양수 && 현재 원소가 음수)에 해당하지 않으면arr[i]를ret에 삽입하고i를 1 증가시킵니다.- 충돌 조건에 해당하면 다음을 수행합니다.
x:=ret의 마지막 원소를 꺼내고(pop) 제거합니다.absX:= |x|,absY:= |arr[i]|로 설정합니다.absX == absY이면 두 소행성이 모두 폭발하므로i만 1 증가시킵니다.absX > absY이면 왼쪽 소행성(x)이 살아남으므로x를ret에 다시 삽입하고i를 1 증가시킵니다.absX < absY이면 오른쪽 소행성이 살아남으므로 아무것도 삽입하지 않고(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]
왼쪽으로 이동하는 -4가 10과 충돌하지만 크기가 작아 폭발하고, 같은 방향으로 움직이는 5와 10은 그대로 남게 됩니다.
복잡도 분석
각 소행성은 최대 한 번 push되고 한 번 pop되므로 시간 복잡도는 O(n)이며, 결과를 저장하기 위한 공간 복잡도 역시 O(n)입니다.