Leetcode 735) Asteroid Collision

19 May 2021 in Algorithms

• stack empty를 for문 앞부분에서 체크해주고, 값을 push 해준다.
• 현재 값이 양수면 쉽다. 그 전값이 음수든 양수든 그냥 값을 push해주면 된다.
• 현재 값이 음수면,
  • 그 전 값이 음수일때는 추가를,
  • 양수일 때는 값을 비교해서 음수의 절댓값이 큰 동안 stack을 pop 을 해준다. 그 후,
    • 스택이 empty면 현재값을 push
    • 스택 peek이 양수고, 현재 음수의 절댓값이 더 작으면 아무일도 안 일어남
    • 스택 peek이 양수고,현재 음수의 절댓값과 같으면, pop을한다.
    • 스택 peek이 음수고, 현재 값이 음수면 push를 한다.

import java.util.*;
class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        if(asteroids.length==1){
            return asteroids;
        }
        Stack<Integer> s = new Stack<>();
        s.push(asteroids[0]);
        boolean notBreak=true;
        for(int i=1;i<asteroids.length;i++){
            if(s.empty()){
                s.push(asteroids[i]);
            }else{
                if(asteroids[i]>0){
                    if(s.peek()>0||s.peek()<0 ){
                        s.push(asteroids[i]);
                    }
                }else if(asteroids[i]<0){
                    if(s.peek()<0){
                        s.push(asteroids[i]);
                    }else{
                        //이러면.. 음수일때도 pop될 수 있으니까?
                        while(s.peek()<-asteroids[i] && s.peek()>0){
                            s.pop();
                            if(s.empty()){
                                break;
                            }
                        }
                        if(s.empty()){
                            s.push(asteroids[i]);                    
                        }else if(s.peek()<0){
                            s.push(asteroids[i]);                               
                        }else if(s.peek()==-asteroids[i]){
                            s.pop();
                        }
                    }
                }
            }
        }
        int[] result = s.stream().mapToInt(i->i).toArray();
        return result;
    }
}

다른 풀이

class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        int i=0;
        int j=1;
        int n= asteroids.length;
        while(j<n){
            if(i>=0 && asteroids[i]>0 && asteroids[j]<0){
                if(asteroids[i]==Math.abs(asteroids[j])){
                    i--;
                    j++;
                } else if(asteroids[i]>Math.abs(asteroids[j])){
                    j++;
                } else{
                    i--;
                }
            } else{
                asteroids[i+1]= asteroids[j];
                i++;
                j++;
            }
        }
        int[] ans= new int[i+1];
        for(int k=0;k<=i;k++)
            ans[k]=asteroids[k];
        return ans;
    }
}

class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        Stack<Integer> stack = new Stack<>();
        for(int i:asteroids){
            if(stack.isEmpty() || stack.peek()<0 || i>0)
                stack.push(i);
            else {
                while(!stack.isEmpty()){
                    if(stack.peek() >= Math.abs(i) || stack.peek()<0){
                        break;
                    } else 
                        stack.pop();
                }
                if(!stack.isEmpty() && stack.peek() == Math.abs(i))
                    stack.pop();
                else if(stack.isEmpty() || stack.peek()<0)
                    stack.push(i);
            }
        }
        int[] res=new int[stack.size()];
        for(int i=res.length-1;i>=0;i--)
            res[i]=stack.pop();
        return res;
    }
}