[LeetCode] 735. Asteroid Collision - Java

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

Asteroid Collision - LeetCode

---

문제

We are given an array asteroids of integers representing asteroids in a row.

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 에서 양수값과 음수값은 각각 오른쪽으로 움직이는 소행성, 왼쪽으로 움직이는 소행성을 나타내고 각 요소의 절대값은 소행성의 크기를 나타낸다.
각 소행성들은 모두 같은 속도로 움직이고 소행성끼리 부딫히게 되었을 때 크기가 같으면 모두 파괴되고 크기가 다른 경우 크기가 작은 소행성이 파괴된다.
이 때 파괴될 수 있는 모든 소행성이 파괴된 후 남은 소행성을 구하는 문제이다.

각 소행성 간의 비교를 위해 Stack을 사용한다.

Stack<Integer> stack = new Stack<>();

 

소행성 배열의 각 요소를 차례대로 탐색하며 각 값에 따라 처리한다.

우선 소행성 값이 양수인 경우에는 stack에 값을 추가한다.

반대로 소행성 값이 음수인 경우에는 stack에 값이 남아있지 않거나 현재 소행성의 크기가 stack의 가장 마지막 소행성의 크기 이하가 될 때 까지 stack에서 값을 꺼내어 소행성이 파괴되었음을 처리한다.

첫 번째 처리 과정을 거친 후 stack이 비어있거나 stack의 마지막 값이 음수값인 경우에는 현재 소행성 값을 stack에 추가한다.
만약 stack에 양수값이 남아있고 비교할 두 소행성의 크기가 같은 경우에는 두 소행성을 모두 파괴 처리한다.

// 모든 소행성 탐색
for(int asteroid : asteroids) {
    // 소행성 값이 양수인 경우(= 오른쪽으로 움직이는 소행성)
    if(asteroid > 0) {
        // stack에 값 추가
        stack.push(asteroid);
    }
    // 소행성 값이 음수인 경우(= 왼쪽으로 움직이는 소행성)
    else {
        // stack에 비교할 양수 값이 남아있고
        // stack의 가장 위에 있는 소행성의 크기 이하가 될 때까지 소행성 파괴
        while(!stack.isEmpty() && stack.peek() > 0 && stack.peek() < -asteroid) {
            stack.pop();
        }
        // 더 이상 stack에 비교할 양수 값이 남아있지 않은 경우
        if(stack.isEmpty() || stack.peek() < 0) {
            // stack에 값 추가
            stack.push(asteroid);
        }
        // 비교할 두 소행성의 사이즈가 같은 경우
        else if(stack.peek() == -asteroid) {
            // 두 소행성 모두 파괴
            stack.pop();
        }
    }
}

 

최종적으로 stack을 배열로 변환하여 반환한다.

// Array 형태로 return
return stack.stream().mapToInt(Integer::intValue).toArray();

 

---

최종 코드

class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        Stack<Integer> stack = new Stack<>();
        
        // 모든 소행성 탐색
        for(int asteroid : asteroids) {
            // 소행성 값이 양수인 경우(= 오른쪽으로 움직이는 소행성)
            if(asteroid > 0) {
                // stack에 값 추가
                stack.push(asteroid);
            }
            // 소행성 값이 음수인 경우(= 왼쪽으로 움직이는 소행성)
            else {
                // stack에 비교할 양수 값이 남아있고
                // stack의 가장 위에 있는 소행성의 크기보다 작아질 때까지 소행성 파괴
                while(!stack.isEmpty() && stack.peek() > 0 && stack.peek() < -asteroid) {
                    stack.pop();
                }
                // 더 이상 stack에 비교할 양수 값이 남아있지 않은 경우
                if(stack.isEmpty() || stack.peek() < 0) {
                    // stack에 값 추가
                    stack.push(asteroid);
                }
                // 비교할 두 소행성의 사이즈가 같은 경우
                else if(stack.peek() == -asteroid) {
                    // 두 소행성 모두 파괴
                    stack.pop();
                }
            }
        }
        
        // Array 형태로 return
        return stack.stream().mapToInt(Integer::intValue).toArray();
    }

}

---