735. Asteroid Collision - Java

📜 문제

• 행성의 크기와 방향을 나타내는 정수 배열(`asteroids`)이 주어짐
• 음수는 왼쪽, 양수는 오른쪽으로 이동
• 행성의 인덱스는 상대적인 위치를 나타낸다.
• 같은 방향으로 이동하는 행성을 절대 충돌하지 않는다.
• `행성이 충돌하는 경우` 더 작은 행성만 파괴 되고, 크기가 같으면 둘 다 파괴 된다.

요구사항: 살아남은 소행성들을 출력하기

 

생각하기

어떤 경우에 소행성들이 충돌하는지 알아 보자

방향에 따른 소행성 이동 확인

위 그림에서 보면 `양수, 음수` 순서대로 주어졌을 때만 소행성이 충돌한다.
충돌하는 경우를 알았으니, 예제를 통해서 접근 방식을 알아보자.

 

asteroids = `[-1, -2, 12, 11, 6, 5, -10, 4, -4, 6, 7]` 일 때,

[5,-10] 구간에서 아래와 같이 충돌이 연쇄적으로 발생한다.

1. |5| < |-10| 으로 5 크기의 소행성은 파괴된다.
2. [6] < |-10| 이므로 6 크기의 소행성은 파괴된다.
3. |11| > |-10| 이므로 10 크기의 소행성은 파괴된다.

위 충돌 후 남아 있는 소행성들은 `[ -1, -2, 12, 11, 4, -4, 6, 7 ]` 이 된다.
[4,-4] 구간에서 다시 충돌이 발생하고, 두 소행성의 크기가 동일하므로 둘 다 파괴된다.

결국 살아 남은 소행성들은 `[-1, -2. 12, 11, 6, 7]` 이 된다.

위 예제에서 알 수 있는 규칙

1. 배열 내에서 처음 양수가 나올 때까지의 음수들은 모두 살아남음
2. 양수들은 인덱스가 지났어도 연쇄 충돌로 인해 파괴될 수 있음
👉 양수들을 저장해둘 공간이 필요하다.

나는 `Deque`를 이용해서 양수를 저장했다.

---

🍳 전체 소스 코드

class Solution {
    static List<Integer> list;
        public static int addMinus(int idx, int[] asteroids){
        while (idx<asteroids.length && asteroids[idx]<0){
            list.add(asteroids[idx++]);
        }
        return idx;
    }
    public int[] asteroidCollision(int[] asteroids) {
       Deque<Integer> queue = new ArrayDeque<>();
        list = new ArrayList<>();
        int idx = 0;
        // 처음 양수 찾기
        idx =addMinus(idx,asteroids);
        while (idx < asteroids.length) {

            // 다음 음수 까지 stack에 양수 list 저장
            while (idx<asteroids.length &&  asteroids[idx] > 0) {
                queue.addFirst(asteroids[idx++]);
            }
            if(idx>=asteroids.length) break;
            int cur = asteroids[idx] *-1;
            // 양 음 이므로 stack vs 음수
            while (!queue.isEmpty()) {
                int plus = queue.pop();
                if(plus==cur){
                    idx++;
                    break;
                }
                else if(plus>cur){
                    idx++;
                    queue.addFirst(plus);
                    break;
                }
            }
            if(queue.isEmpty()){
               idx=addMinus(idx,asteroids);
            }
        }
        while (!queue.isEmpty()) {
            list.add(queue.pollLast());
        }
        return list != null ? list.stream().mapToInt(Integer::intValue).toArray() : new int[0];

    }
}

---

✍ 부분 코드 설명

변수 선언 & 처음으로 나오는 양수 찾기

public class N_735 {
    static List<Integer> list;
    public static int addMinus(int idx, int[] asteroids){
        while (idx<asteroids.length && asteroids[idx]<0){
            list.add(asteroids[idx++]);
        }
        return idx;
    }
    public static int[] asteroidCollision(int[] asteroids) {
        Deque<Integer> queue = new ArrayDeque<>();
        list = new ArrayList<>();
        int idx = 0;
        // 처음 양수 찾기
        idx =addMinus(idx,asteroids);
               ...
	}
}

•  `list`: 살아 남은 소행성 저장
• `queue`: 양수 저장
• `addMinus()`: 다음 양수가 나오기 이전의 음수 저장, 양수 위치(`idx`) 반환

---

충돌 다루기

public static int[] asteroidCollision(int[] asteroids) {
			...           
	 while (idx < asteroids.length) {
     		// 다음 음수까지 queue에 양수 저장
            while (idx<asteroids.length &&  asteroids[idx] > 0) {
                queue.addFirst(asteroids[idx++]);
            }
            // 배열의 끝에 도달한 경우 탈출           
            if(idx>=asteroids.length) break;            
            
            int cur = asteroids[idx] *-1;  // 음수 절댓값 저장
            while (!queue.isEmpty()) {          
                int plus = queue.pop();	                
                
                // 크기가 동일한 경우 둘 다 파괴
                if(plus==cur){	
                    idx++;
                    break;
                }
                
                // plus의 크기가 더 큰 경우, cur 소행성 파괴
                else if(plus>cur){
                    idx++;                                       
                    queue.addFirst(plus); // 다시 queue에 저장
                    break;
                }               
            }
            
            // 양수가 없는 경우, 다음 양수까지 음수 소행성들은 살아 남음
            if(queue.isEmpty()){
               idx=addMinus(idx,asteroids);
            }
        }
}

1.  [양수, 음수] 순서일 때만 충돌이 발생하기 때문에 음수가 나올 때까지 queue에 양수들을 저장한다.

`queue.addFirst()`로 삽입해야함.
∵ 충돌 시 나중에 들어온 양수가 먼저 충돌하기 때문

2. `cur`에 음수 저장

3. queue에서 빼낸 `plus`에 양수 저장 & 충돌 처리

• `plus < cur`: plus 박살나고 연쇄 충돌 ㄱㄱ
• `plus == cur`:  둘 다 박살
• `plus>cur`:  cur 박살나고, plus 다시 queue에 넣기

4. 충돌 후 queue에 남아 있는 양수가 없는 경우, 다시 처음으로 나오는 양수 찾기

5. 배열의 끝까지 (1) ~ (4) 과정 반복

---

살아 남은 양수 소행성 삽입

public static int[] asteroidCollision(int[] asteroids) {
                ...
        while (!queue.isEmpty()) {
            list.add(queue.pollLast());
		}
        return list != null ? list.stream().mapToInt(Integer::intValue).toArray() : new int[0];
	}
}

 

queue를 후입선출 방식으로 사용했기 때문에, 맨 뒤에 있는 요소부터 저장해야한다.

반환 값이 `int[]`이므로 list를 배열로 변환해서 반환한다.

---

✨ 결과

충돌하는 경우를 빨리 생각해 내서 쉽게 풀 수 있었다.

나는 선입 선출인 queue를 후입 선출 방식으로 사용하고, list를 int 배열로 반환하는 과정을 거쳤다.

하지만 이 문제는, Stack과 추가적인 int 배열을 사용해 풀 수 있다.
더 가독성이 좋은 코드이므로 아래 더보기 칸에 코드를 넣어두겠다.

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