[leetcode] 735. Asteroid Collision

문제)

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 - 소행성

integer 형태를 띈 소행성 배열이 일렬로 주어진다.

소행성의 절대값은 size이고, sign은 방향을 의미하며 양수는 오른쪽, 음수는 왼쪽이고 소행성은 모두 동일한 속도로 이동한다.

모든 충돌 이후의 소행성들의 상태를 구한다.

두 개의 소행성이 만나면 사이즈가 작은 소행성이 폭발하고 만약 두 개의 사이즈가 같으면 둘다 폭발한다.

같은 방향으로 이동 중인 소행성의 경우 절대 만나지 않는다.

 

최초 풀이)

첫번째 소행성부터 마지막 소행성까지 스택에 넣어가면서 스택 안에 들어있는 소행성들과 충돌 여부를 고려해주며 문제를 풀었습니다.

 

소행성끼리 절대 만나지 않는 경우

1. 방향이 같은 경우

2. 왼쪽 소행성은 음수이고 오른쪽 소행성이 양수일 경우 반대로 이동하기 때문에 만나지 않음

 

1) 방향이 같은지는 곱셈으로 해결했고 위의 경우에 해당될 경우 스택에 곧바로 넣어주었습니다.

 

2) 스택의 last 값의 절대값이 스택에 넣으려는 값의 절대값보다 클 경우 스택에 넣지 않습니다.

 

3) 절대값이 같은 경우는 둘다 폭발하니까 스택에 넣지 않습니다.

4) 스택의 last 값의 절대값이 스택에 넣으려는 값의 절대값보다 작은 경우 위의 상황을 다시 고려합니다.

4-1) 혹시 스택이 비어있다면 스택에 넣으려는 값을 넣어주고 다음 소행성 값을 고려합니다.

 

1, 2) 상황은 스택의 last 값을 peek으로 꺼내와 사용하였고

3) 상황은 스택의 last 값을 pop 해서 사용했습니다.

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

        for(int a: asteroids) {
            if(!stack.empty()) {
                while(!stack.empty()) {
                    int temp = stack.peek();
                    
                    if (temp * a > 0) {
                        stack.push(a);
                        break;
                    }
                    else if (temp < 0 && a > 0) {
                        stack.push(a);
                        break;
                    }
                    else if (Math.abs(temp) > Math.abs(a)) {
                        break;
                    }
                    else {
                        temp = stack.pop();
                        if (temp + a == 0) {
                            break;
                        }
                        if (stack.size() == 0) {
                            stack.push(a);
                            break;
                        }
                    }
                }
            } else {
                stack.push(a);
            }
        }
        
        int[] result = new int[stack.size()];
        for(int i = 0; i < stack.size(); i++) {
            result[i] = stack.get(i);
        }

        return result;
    }
}