[LeetCode- Part. 3] 2. 소행성 충돌

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

Asteroid Collision - LeetCode

 

1. 양수는 오른쪽, 음수는 왼쪽으로 이동

2. 둘이 만날 경우 조건 분기

(1) 같을 경우 둘다 파괴

(2) 절댓값이 큰 경우가 남는다.

 

class Solution {
    public int[] asteroidCollision(int[] arr) {
        Stack<Integer> stack = new Stack<>();
        for(int i=0;i<arr.length;i++){
            if(arr[i]>0) stack.push(arr[i]);
            if(!stack.isEmpty()&&arr[i]<0){
                int size= stack.size();
                boolean flag=true;
                for(int j=0;j<size;j++){
                    if(stack.peek()>0){
                        if(Math.abs(stack.peek())<Math.abs(arr[i])){
                          stack.pop();
                            flag=true;
                        } 
                        else if(Math.abs(stack.peek())==Math.abs(arr[i])) {
                            stack.pop();
                            flag=false;
                            break;
                        }
                        else if(Math.abs(stack.peek())>Math.abs(arr[i])) {
                            flag=false;
                        }
                    }
                }
                if(flag)stack.push(arr[i]);
            }
            else if(stack.isEmpty() && arr[i]<0) stack.push(arr[i]);
        }
        int[]answer=new int[stack.size()];
        int cnt=0;
        for(int x: stack) answer[cnt++]=x;
        return answer;
    }
}

 

class Solution {
    public int[] asteroidCollision(int[] arr) {
        Stack<Integer> stack = new Stack<>();
        for(int i=0;i<arr.length;i++){
            boolean flag=true;
            if(arr[i]>0) stack.push(arr[i]);
            if(!stack.isEmpty()&&arr[i]<0){
                int size= stack.size();
                for(int j=0;j<size;j++){
                    if(stack.peek()>0){
                        if(Math.abs(stack.peek())<Math.abs(arr[i])){
                            stack.pop();
                            flag=true;
                        } 
                        else if(Math.abs(stack.peek())==Math.abs(arr[i])) {
                            stack.pop();
                            flag=false;
                            break;
                        }
                        else if(Math.abs(stack.peek())>Math.abs(arr[i])) {
                            flag=false;
                        }
                    }
                }
            }
            if(flag&&arr[i]<0) stack.push(arr[i]);
        }
        int[]answer=new int[stack.size()];
        int cnt=0;
        for(int x: stack) answer[cnt++]=x;
        return answer;
    }
}

 

 

+) 세련된 풀이

class Solution {
    public int[] asteroidCollision(int[] arr) {
        //1. ds
        Stack<Integer> s = new Stack<>();
        
        //2. loop
        for(int i:arr){
            if(0<i){
                s.push(i);
            }else{
                //음수 일경우
                //비어있지 않으면 반복하는데 0보다 크고, 현재 값의 절댓값이 더 크면, 스택에서 제거한다.
                while(!s.isEmpty()&&s.peek()>0 &&s.peek()<Math.abs(i)){
                    s.pop();
                }
                //비었을 때나 스택에 음수만 있으면 삽입.
                if(s.isEmpty()|| s.peek()<0){
                    s.push(i);
                }
                //방향은 다르고 절댓값은 같은 경우
                else if(i+s.peek()==0){
                    s.pop();
                }
            }
        }
        
        //스택을 배열에 넣을 때는 맨 뒷칸부터 넣는다.
        int[] answer = new int[s.size()];
        for(int i=answer.length-1; i>=0; i--){
            answer[i]=s.pop();
        }
        return answer;
    }
}