[LeetCode-155] List.remove(Integer)가 remove(int)랑 다르게 동작한다

스택·큐 개념과 자주 쓰는 메서드는 카테고리 총정리 글에서 다룬다. 처음 보는 “보조 스택으로 추가 정보 유지” 패턴.

• 문제 링크: https://leetcode.com/problems/min-stack/
• 파일 경로: src/main/java/coding_test/스택_큐/LC0155_MinStack.java
• 난이도: Medium

문제 설명

push/pop/top/getMin(최솟값 조회) 전부를 O(1)에 처리하는 MinStack을 설계한다.

push(-2); push(0); push(-3);
getMin(); // -3
pop();
top();    // 0
getMin(); // -2

시행착오

처음엔 ArrayList로 접근했다 — push는 add, pop은 remove, getMin은 매번 리스트 전체를 for로 훑어서 최솟값을 찾는 방식이었다. 테스트는 다 통과했지만 두 가지 문제가 있었다.

1. getMin()이 O(n)이었다. 이 문제의 핵심 조건이 “모든 연산을 O(1)에”인데, 매번 전체를 훑는 건 그 조건을 지키지 못한 것이었다.

2. list.remove(list.get(list.size() - 1))에 숨어있던 버그. List.remove()에는 remove(int index)와 remove(Object o) 두 가지가 있는데, list.get(...)이 반환하는 건 Integer(객체)라서 자바가 remove(Object o)로 해석해버렸다. 그러면 “맨 뒤 원소”가 아니라 “그 값이 처음 나오는 위치”를 지운다. push(1), push(2), push(1) 다음 pop()을 하면 마지막에 넣은 1이 아니라 처음 넣은 1이 지워지는 걸 직접 테스트로 확인했다 — 평범한 예제들로는 안 드러나는 버그였다.

결국 “보조 스택으로 추가 정보를 같이 유지한다”는 새 패턴을 수도코드로 받아서 다시 짰다 — 값을 담는 스택과, 그 시점까지의 최솟값을 매번 같이 기록하는 보조 스택을 나란히 두는 방식이다.

최종 코드

public class LC0155_MinStack {
    private Deque<Integer> stack;
    private Deque<Integer> minVal_Stack;

    public LC0155_MinStack() {
        stack = new ArrayDeque<>();
        minVal_Stack = new ArrayDeque<>();
    }

    public void push(int val) {
        stack.push(val);
        if (minVal_Stack.isEmpty()) {
            minVal_Stack.push(val);
        } else {
            minVal_Stack.push(Math.min(val, minVal_Stack.peek()));
        }
    }

    public void pop() {
        stack.pop();
        minVal_Stack.pop();
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minVal_Stack.peek();
    }
}

오늘 배운 내용

List.remove()는 인자 타입에 따라 완전히 다른 연산을 고른다. int를 넘기면 인덱스로, Integer(객체)를 넘기면 값으로 찾아서 지운다. list.get(...)의 반환형이 Integer라는 걸 의식하지 않으면, “맨 뒤를 지운다”는 의도가 조용히 “그 값을 지운다”로 바뀌어버린다.

그리고 “매번 다시 계산하지 않고, 변할 때마다 보조 자료구조에 미리 기록해둔다”는 게 이번에 새로 배운 패턴이다. getMin()을 호출할 때 찾는 게 아니라, push()할 때마다 “지금까지의 최솟값”을 보조 스택에 같이 쌓아두면, 나중에 조회는 그냥 꺼내보기만 하면 끝난다.

오답노트

• 틀렸던 패턴 1: getMin()에서 리스트 전체를 매번 순회 — O(1) 조건 위반.
• 틀렸던 패턴 2: list.remove(list.get(size-1)) — Integer 객체를 넘겨서 remove(Object)로 해석됨, 값이 중복되면 잘못된 위치가 지워짐.
• 왜 틀렸나: List.remove()의 두 오버로드(int vs Object)를 구분하지 않고, “인덱스를 넘겼다”고 생각했지만 실제로는 박싱된 객체를 넘기고 있었다.
• 고친 패턴: 보조 스택(minVal_Stack)으로 최솟값을 매번 같이 기록, Deque의 push/pop/peek만 사용(인덱스 기반 remove 자체를 안 씀).
• 다음에 떠올릴 시점: List에서 “인덱스로 지우고 싶다”는 의도가 있을 때, 넘기는 값이 진짜 int 리터럴/변수인지 Integer 객체인지 한 번 더 확인한다. 그리고 “매번 다시 계산하는” 코드를 보면, “변경되는 시점에 미리 기록해두면 안 될까”부터 의심한다.

AI라면 어떻게 풀었을까

보조 스택에 “그 시점의 최솟값”을 매번 통째로 저장하는 대신, 그 값이 현재 최솟값을 경신했을 때만 보조 스택에 쌓는 방식도 가능하다.

public class LC0155_MinStack {
    private Deque<Integer> stack = new ArrayDeque<>();
    private Deque<Integer> minStack = new ArrayDeque<>();

    public void push(int val) {
        stack.push(val);
        if (minStack.isEmpty() || val <= minStack.peek()) {
            minStack.push(val);
        }
    }

    public void pop() {
        if (stack.pop().equals(minStack.peek())) {
            minStack.pop();
        }
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}

지금 버전은 push할 때마다 minVal_Stack에 무조건 하나씩 쌓아서 두 스택의 크기가 항상 같다. 이 버전은 최솟값이 갱신될 때만 minStack에 쌓기 때문에, 최솟값이 자주 안 바뀌는 입력에서는 minStack이 훨씬 작아진다 — 메모리를 아끼는 변형이다. 다만 pop()할 때 “지금 꺼낸 값이 최솟값이었는지”를 확인하는 조건이 하나 더 필요해진다는 차이가 있다.