leetcode link

Description

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.

---

asteroids는 한 줄에 있는 운석을 나타내는 정수 배열입니다.

각 운석마다 절대값은 크기를 나타내고, 부호는 방향을 나타냅니다 (양수는 오른쪽으로, 음수는 왼쪽으로). 각 운석은 동일한 속도로 이동합니다.

모든 충돌 후 운석의 상태를 알아내세요. 두 운석이 만나면 더 작은 것이 폭발합니다. 크기가 같은 경우 둘 다 폭발합니다. 같은 방향으로 이동하는 두 운석은 결코 만나지 않습니다.

예시1:

입력: asteroids = [5,10,-5]
출력: [5,10]
설명: 10과 -5가 충돌하여 10이 남습니다. 5와 10은 결코 충돌하지 않습니다.

예시2:

입력: asteroids = [8,-8]
출력: []
설명: 8과 -8이 충돌하여 서로 폭발합니다.

예시3:

입력: asteroids = [10,2,-5]
출력: [10]
설명: 2와 -5가 충돌하여 -5가 남습니다. 10과 -5가 충돌하여 10이 남습니다.

+예시4:

입력: asteroids = [-5, 10]
출력: [-5, 10]
설명: -5는 왼쪽, 10은 오른쪽으로 가기에 서로 충돌하지 않습니다.

제한 사항:

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

Solution

import java.util.Stack;

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

        for (int asteroid : asteroids) {
            // 우측으로 이동하는 경우는 그냥 스택에 넣음
            if (asteroid > 0) {
                stack.push(asteroid);
            } else {
                // 스택에 있는 우측으로 이동 중인 로봇들을 모두 처리
                while (!stack.isEmpty() && stack.peek() > 0 && stack.peek() < Math.abs(asteroid)) {
                    stack.pop();
                }
                // 충돌이 발생하지 않는 경우
                if (stack.isEmpty() || stack.peek() < 0) {
                    stack.push(asteroid);
                } else if (stack.peek() == Math.abs(asteroid)) { // 크기가 같은 경우
                    stack.pop();
                }
            }
        }

        return stack.stream().mapToInt(Integer::intValue).toArray();
    }
}