[LeetCode] 735. Asteroid Collision 문제 풀이

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

 

📌 문제 요약

정수 배열로 소행성이 주어짐. (asteroids)

각 정수의 절대값은 소행성의 크기이며, 크기와 상관 없이 속도는 동일함.

부호는 방향을 나타냄.

• 양수 : 오른쪽으로 이동
• 음수 : 왼쪽으로 이동

두 소행성이 충돌할 때 크기가 작은 쪽이 파괴되고, 크기가 같으면 둘 다 파괴됨.

모든 충돌이 끝난 후 남아있는 소행성을 반환해야 함.

 

 

💡 풀이 포인트

스택의 맨 위 소행성이 음수인 경우, 다음 소행성과 만날 일 없음.

그렇기 때문에 맨 위 소행성이 양수일 때에 대해서만 체크해서 없애면 됨.

 

 

✅ 풀이 방법

두 단계로 나눠서 pop 먼저 하고 push를 하였습니다.

 

1. pop 하기 위한 조건
   1. 스택 맨 위 소행성이 양수이고
   2. 그 다음 소행성이 음수이고
   3. 스택 맨 위 소행성의 절대값이 그 다음 소행성 절대값보다 작거나 같을 때
2. push 하기 위한 조건 (or)
   1. 스택이 비어 있거나 (처음 넣거나 소행성이 다 제거된 경우)
   2. 스택 맨 위 소행성이 음수이거나
   3. 그 다음 소행성이 양수인 경우
   4. 두 소행성이 충돌하지 않았을 때 (asteroid != 0)

두 절대값이 동일해서 둘 다 파괴된 경우는 스택에 추가하지 않고 넘어가야 하기 때문에 asteroid를 0으로 초기화 하는 코드를 작성하였습니다.

 

그리고 int 배열로 반환해야 하므로 int[] result에 담았습니다.

 

 

🔎 시간 복잡도

배열의 모든 원소를 최대 한 번씩만 스택에 넣고 빼기 때문에 O(n)

(n : asteroids 배열의 길이)

 

🔍 공간 복잡도

최악의 경우 모든 원소가 충돌 없이 그대로 스택에 남게 될 수 있으므로 O(n)

(n : asteroids 배열의 길이)

 

 

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

        for (int asteroid : asteroids) {
            // If the last element in the stack is negative, there's no need to check for collisions.
            // This is because both rocks are moving left, so they can't explode.
            // That's why we only check for collisions when the top of the stack is positive.

            // 1. Remove
            while (!stack.isEmpty() && stack.peek() > 0 && asteroid < 0) {
                // Since we know which is negative, no need to use 'Math.abs()'.
                if (stack.peek() < -asteroid) {
                    stack.pop();
                    // Keep comparing
                    continue;
                }
                else if (stack.peek() == -asteroid) {
                    stack.pop();
                    // Both exploded. (Terminate the loop and reset asteroid)
                    asteroid = 0;
                }
                break;
            }

            // 2. Add (After all the smaller, exploded asteroids had been removed)
            if (stack.isEmpty() || stack.peek() < 0 || asteroid > 0) {
                if (asteroid != 0) {
                    stack.push(asteroid);
                }
            }
        }

        int[] result = new int[stack.size()];
        for (int i = 0; i < stack.size(); i++) {
            result[i] = stack.get(i);
        }
        return result;
    }
}