[LeetCode] Asteroid Collision

https://leetcode.com/problems/asteroid-collision/description/?envType=study-plan-v2&envId=leetcode-75

 

We are given an array asteroids of integers representing asteroids in a row. The indices of the asteriod in the array represent their relative position in space.

For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). Each asteroid moves at the same speed.

Find out the state of the asteroids after all collisions. If two asteroids meet, the smaller one will explode. If both are the same size, both will explode. Two asteroids moving in the same direction will never meet.

Example 1:
Input: asteroids = [5,10,-5]
Output: [5,10]
Explanation: The 10 and -5 collide resulting in 10. The 5 and 10 never collide.

Example 2:
Input: asteroids = [8,-8]
Output: []
Explanation: The 8 and -8 collide exploding each other.

Example 3:
Input: asteroids = [10,2,-5]
Output: [10]
Explanation: The 2 and -5 collide resulting in -5. The 10 and -5 collide resulting in 10.
 

Constraints:
2 <= asteroids.length <= 104
-1000 <= asteroids[i] <= 1000
asteroids[i] != 0

---

숫자가 들어간 배열이 있다.
배열의 인덱스들은 우주의 상대적인 위치를 나타낸다.
각 소행성의 절대값은 소행성의 크기를 나타낸다.
양수는 오른쪽, 음수는 왼쪽으로 이동함을 나타낸다.
모든 소행성은 동일한 속력으로 운동한다.
충돌이 모두 끝난 후 소행성들의 상태를 리턴
충돌이 일어났을 때 작은 사이즈는 폭발한다. 동일한 사이즈면 둘다 폭발한다.
같은 방향으로 움직이는 두 소행성은 만나지 않는다.

 

단순한 듯 하면서도 뭔가 복잡하다!

진짜 어려운 건지, 이상하게 머리가 안 돌아가서 그랬던 건지 아무튼 되게 오래 잡고 있었던 문제..

아래 힌트를 읽고 겨우 어떻게 어떻게 풀어내긴 했다.

Say a row of asteroids is stable. What happens when a new asteroid is added on the right?

소행성 배열이 정적이라고 해 보자. 만약 오른쪽에서 새로운 소행성이 추가된다면 무슨 일이 일어날까?

 

 

이걸 읽고, stack이라는 배열을 새로 만들어 매번 stack에 현재 소행성을 추가해 준다.

그리고 stack 배열을 맨 끝에서부터 돌아서 소행성끼리 비교를 한 후 지울 건 지우고.. 넘어갈 건 넘어가 준다.

const asteroidCollision = (a) => {
    let i = 0;
    let length = a.length;
    let stack = [];
    let left, right;
    for(let i=0; i<length; i++){
        stack.push(a[i]);
        for(let j=stack.length-1; j>-1; j--){
            left = stack[j-1];
            right = stack[j];
            if(left && left > 0 && right < 0){
                // 왼쪽이 양수, 오른쪽이 음수 -> 만남
                if(left + right > 0){
                    // 왼쪽이 이김, 오른쪽 제거
                    stack.pop();
                }
                if(left + right == 0){
                    // 둘 다 제거
                    stack.pop();
                    stack.pop();
                }
                if(left + right < 0){
                    // 오른쪽이 이김, 왼쪽 제거
                    stack.splice(j-1 ,1);
                }
            }
        }
    }
    
    return stack;
};

하지만 이렇게 하면 당연히 효율이 엄청나게 떨어진다^_^;

무작정 결과 배열에 현재 소행성을 넣지 말고 넣기 전에 검사부터 하고 넣었으면 더 효율적이었을 듯.

자칫하면 제곱으로 돌게 될 수도ㅋㅋㅋ

 

 

그래서 이번에도 가져온 1등 코드.

var asteroidCollision = function(asteroids) {
  let result = [];
    let index = 0; 

    for (let i = 0; i < asteroids.length; i++) {
        let current = asteroids[i];

        while (
            index > 0 &&
            result[index - 1] > 0 &&
            current < 0
        ) {
            if (result[index - 1] < -current) {
                index--;
                result.pop(); 
            } else if (result[index - 1] === -current) {
                index--;
                result.pop();
                current = 0; 
                break;
            } else {
                current = 0;
                break;
            }
        }

        if (current !== 0) {
            result[index] = current;
            index++;
        }
    }

    return result;
};

일단 결과를 내보낼 result와 result 내부를 끝에서부터 탐색하기 위한 인덱스를 선언해 주고,

현재 확인해야 할 소행성을 current에 저장하고 while문 안으로 들어간다.

 

단, 1) result에 엘리먼트가 있고

      2) 최근에 들어간 행성이 양수(오른쪽 이동)이며,

      3) 현재 들어갈 소행성이 음수일 때만 반복문으로 들어간다. -> 충돌이 일어날 때만!

 

while문 안에 들어가지 않은 경우 현재 index 위치에 소행성을 넣어 주고, index++를 해 준다.

 

while문 안에 들어오면 충돌 판정을 해서...

오른쪽 에 있는 행성이 살아남은 경우 index-- 한 후 가장 최근에 들어간 소행성을 제거한다.

두 행성이 만나 둘 다 사라진 경우, 가장 최근에 들어간 소행성을 제거하고 루프를 종료한다.

왼쪽에 있는 행성이 살아남은 경우에는 현재 소행성을 추가하지 않도록 처리하고 루프를 종료한다.

current를 굳이 0으로 만들어 주는 이유는 while문이 끝난 후에 제거될 소행성을 result에 넣지 않기 위해서이다.

 

그리고 while문이 종료되면.. 살아남은 행성(current)을 result에 넣어 주고 다음 루프로 들어간다.

깔끔하다.. while문에 들어가는 조건 자체도 굉장히 효율적이다. ㅇ_ㅇ 어떻게 이런 생각을?

 

 

그와 별개로, 솔루션을 정리해 둔 한 분의 답안도 가져와 본다.

코딩닌자(ㅋㅋ)라는 분인데, 유튜브 채널도 운영하시는 듯.

https://leetcode.com/problems/asteroid-collision/solutions/5756593/video-using-stack-to-keep-asteroids

var asteroidCollision = function(asteroids) {
    const res = []
    
    for (let i = 0; i < asteroids.length; i++) {
        const last = res[res.length - 1]
        const cur = asteroids[i]
        
        if (!res.length || last < 0 || cur > 0) {
            res.push(cur)
        } else if (-cur == last) {
            res.pop()
        } else if (-cur > last) {
            res.pop()
            i--
        }
    }
    
    return res  
};

 

이 분도 로직 자체는 동일한데 그냥 반복문을 초기 배열 길이만큼 한 바퀴만 돌면 끝난다는 점이 다르다.

내가 구현하고 싶었던 것도 이런 방식이었는데.. 추구미와 도달가능미를 이렇게 대놓고 마주하니 기분이 미묘하다.