[LeetCode] 735. Asteroid Collision (해석, Java 풀이)

문제

https://leetcode.com/problems/asteroid-collision/

주어진 `asteroids` 배열은 연속한 소행성(asteroid)을 나타내는 정수로 이루어져있다. 

각 소행성의 절대값은 이것의 사이즈를 나타내고, 부호는 방향을 나타낸다(+는 오른쪽, -는 왼쪽). 소행성들은 같은 속도로 움직인다.

모든 충돌이 끝난 후의 소행성의 상태를 반환하라. 만약 두 소행성이 만난다면, 더 작은 것이 폭발한다. 만약 두 소행성이 같은 크기라면, 모두 폭발한다. 같은 방향으로 움직이는 두 소행성은 절대 만나지 않는다.

 

풀이

class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        ArrayDeque<Integer> st = new ArrayDeque<>();

        for (int asteroid : asteroids) {
            if (st.isEmpty() || asteroid > 0) {
                st.push(asteroid);
            } else {
                while (!st.isEmpty() && st.peek() > 0 && Math.abs(asteroid) > st.peek()) {       // 스택 원소 제거
                    st.pop();
                }

                if (!st.isEmpty() && Math.abs(asteroid) == st.peek()) {
                    st.pop();
                } else if (st.isEmpty() || st.peek() < 0) {
                    st.push(asteroid);
                }
            }
        }

        int[] result = new int[st.size()];
        for (int i = st.size() - 1; i >= 0; i--) result[i] = st.pop();

        return result;
    }
}

문제를 이해하기 굉장히 어려웠다. 스택의 개념을 넣어야 이해가 편했다.

스택의 가장 위 원소와 현재 원소의 부호가 다를 경우엔 무조건 최신 원소부터 충돌한다. 

1. 스택에는 최대한 하나의 부호만 넣는다. (나는 +를 선택했다)
2. 스택이 비었거나, 현재 소행성이 + 이면 스택에 넣는다. ( 스택 내부에 있는 원소들도 모두 + 일테니.. )
3. 현재 소행성이 - 이고, 스택의 최상위 원소가 + 이면서, 현재 소행성의 절댓값이 더 크다면,
   스택 최상단 소행성은 충돌되어 없어지므로, 최상단 원소를 제거한다. 
    -> 조건을 만족하지 않을 때까지 반복한다. 
4. 해당 소행성으로 스택 내부에 pop()은 완료하였으므로, 해당 소행성을 넣을지 말지를 결정한다.
   1. 절대값이 같다면, 둘 다 폭발하므로 스택 최상단 소행성도 pop
   2. 스택이 비었거나, 스택 내부 원소가 -밖에 남지 않았다면 현재 소행성도 stack으로 push

 

시간 복잡도: O(n), 공간 복잡도: O(n)

https://github.com/jeongum/java-algorithm/blob/d22448a77ba632a7b66c09ab815ee64061c4b6eb/stack/LeetCode_735_AsteroidCollision.java