735. Asteroid Collision

📌 문제 링크 :

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

 

✅ 내 풀이(Success) :

class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        Stack<Integer> stack = new Stack<>();
        for (int curr: asteroids) {
            if (stack.isEmpty()) {
                stack.push(curr);
            } else {
                boolean addable = true;
                while (!stack.isEmpty()) {
                    int top = stack.peek();
                    if (top > 0 && curr < 0) {
                        int absTop = Math.abs(top);
                        int absCur = Math.abs(curr);
                        if (absTop == absCur) {
                            stack.pop();
                            addable = false;
                            break;
                        } else if (absTop < absCur) {
                            stack.pop();
                        } else {
                            addable = false;
                            break;
                        }
                    } else {
                        stack.push(curr);
                        addable = false;
                        break;
                    }
                }
                if (addable) {
                    stack.push(curr);
                }
            }
        }

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

 

🔨 리팩토링 :

class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        // 오른쪽 끝이 마지막 요소가 되도록 Deque 사용
        Deque<Integer> deque = new ArrayDeque<>();

        for (int curr : asteroids) {
            // 양수(오른쪽으로 이동)는 충돌 없이 그냥 추가
            if (curr > 0) {
                deque.addLast(curr);
                continue;
            }

            // curr가 음수인 경우: deque 끝에 양수가 존재하는 동안만 충돌 가능
            boolean alive = true;
            while (alive && !deque.isEmpty() && deque.peekLast() > 0) {
                int top = deque.peekLast();

                // top > 0, curr < 0 이므로 top + curr 비교로 절댓값 비교를 대체
                int sum = top + curr;
                if (sum == 0) {
                    // 같은 크기: 둘 다 파괴
                    deque.removeLast();
                    alive = false;
                } else if (sum < 0) {
                    // |top| < |curr|: deque의 마지막이 파괴되고 curr는 계속 충돌 가능
                    deque.removeLast();
                    // loop 계속
                } else {
                    // |top| > |curr|: curr가 파괴
                    alive = false;
                }
            }

            if (alive) {
                // 충돌 후에도 살아남았거나 충돌 대상이 없는 경우 추가
                deque.addLast(curr);
            }
        }

        // Deque를 배열로 변환 (왼쪽 -> 오른쪽 순서 유지)
        int n = deque.size();
        int[] result = new int[n];
        int idx = 0;
        for (int v : deque) {
            result[idx++] = v;
        }
        return result;
    }
}

 

🧐 리뷰 :

 이 문제를 Stack을 사용해 구현했지만, 코드를 다시 보니 조건문이 중첩되고 Math.abs() 연산이 반복되어 가독성이 다소 떨어졌다. 그래서 GPT의 도움을 받아 리팩토링을 진행했다.

 

 GPT는 우선 Stack 대신 Deque(ArrayDeque)를 사용하도록 제안했는데, 이는 동기화 오버헤드를 줄이면서 스택 연산을 더 명확하게 표현할 수 있는 선택이었다. 또한 Math.abs()를 반복 호출하는 대신 top + curr 연산을 통해 절댓값 비교를 단순화했고, 충돌 여부를 관리하던 addable 변수를 alive로 바꿔 의미를 더 직관적으로 표현했다.

내 코드는 동작은 올바르지만 로직 흐름이 복잡하고 조건 분기가 많았던 반면, 리팩토링된 코드는 불필요한 코드 중복을 제거하고 각 조건의 의도가 명확하게 드러나도록 정리되어 있었다. 무엇보다 코드의 흐름이 자연스럽게 읽히고, 충돌 로직이 소행성이 ‘살아남는가 / 파괴되는가’라는 관점으로 단순화되어 이해하기 쉬워졌다.

 

 이번 경험을 통해 단순히 문제를 해결하는 것뿐만 아니라, 코드의 구조를 개선하고 더 나은 자료구조를 선택하는 과정이 얼마나 중요한지를 다시 느꼈다.