[LeetCode/Top Interview 150] [Stack] 155. Min Stack

문제 링크: https://leetcode.com/problems/min-stack/?envType=study-plan-v2&envId=top-interview-150
사용 언어: Java(OpenJDK 17. Java 8)

난이도: medium

문제:

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

MinStack() initializes the stack object.
void push(int val) pushes the element val onto the stack.
void pop() removes the element on the top of the stack.
int top() gets the top element of the stack.
int getMin() retrieves the minimum element in the stack.
You must implement a solution with O(1) time complexity for each function.

Example 1:

Input
["MinStack","push","push","push","getMin","pop","top","getMin"][],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top(); // return 0
minStack.getMin(); // return -2

Constraints:

-2^31 <= val <= 2^31 - 1
Methods pop, top and getMin operations will always be called on non-empty stacks.
At most 3 * 10^4 calls will be made to push, pop, top, and getMin.

전략:

int 요소를 저장하는 스택 자료구조를 구현하되 각 함수의 실행 시간이 O(1)이어야 한다.
getMin 같은 경우도 요소 중에서 min값을 가지는 요소를 O(1) 시간 안에 리턴해줘야한다.
Stack인 만큼 순서가 보장되므로 삽입 시점의 min 값을 같이 저장해 주도록 하겠다.
내부적으로는 그냥 기존 Stack을 활용해서 구현하면 거의 수정할 필요 없이 기존 Stack의 함수를 호출하는 수준으로 구현 가능할 거 같다.
pop, top and getMin 함수는 항상 비어있지 않은 스택에서만 호출된다는 전제가 있기도 하고, 내부적으로 Stack을 사용하므로 RuntimeError(Stack Overflow, Stack Underflow) 발생시 어차피 내부의 Stack에서 해당 에러를 처리할 테니 걱정하지 않기로 했다.

코드 구현:

class MinStack {
    Stack<Integer[]> internal_stack;

    public MinStack() {
        internal_stack = new Stack<Integer[]>();
    }
    
    public void push(int val) {
        internal_stack.push(new Integer[] {val, Math.min(getMin(), val)});
    }
    
    public void pop() {
        internal_stack.pop();
    }
    
    public int top() {
        return internal_stack.peek()[0];
    }
    
    public int getMin() {
        if (internal_stack.size()==0) return Integer.MAX_VALUE;
        return internal_stack.peek()[1];
    }
}

실행결과:
Time: 4 ms (99.2%), Space: 47 MB (78.01%) - LeetHub
https://github.com/1-vL/LeetCode/blob/main/0155-min-stack/0155-min-stack.java

개선 방안:

기존 Stack을 사용하면 안 된다는 얘기는 없었긴 한데 너무 구현한 내용이 없어서 이래도 되는가 싶기는 하다.
성능 자체는 더 이상 개선할 만한 방식이 생각나지는 않는다.

Solutions 탭의 타인 코드:

class MinStack {
    int min = Integer.MAX_VALUE;
    Stack<Integer> stack = new Stack<Integer>();
    public void push(int x) {
        // only push the old minimum value when the current 
        // minimum value changes after pushing the new value x
        // 새로 입력받은 x가 기존 min 값 이하인 경우에만 기존 min 값을 push한다.
        if(x <= min){          
            stack.push(min);
            min=x;
        }
        // 언제나 새로 받은 x 값을 push 한다.
        stack.push(x);
    }

    public void pop() {
        // if pop operation could result in the changing of the current minimum value, 
        // pop twice and change the current minimum value to the last minimum value.
        // pop실행 결과 기존 min값이 변경된다면, pop을 2번 실행해 min 값을 2번째 pop(push시 저장한 지금 시점의 min값)으로 변경한다.
        if(stack.pop() == min) min=stack.pop();
    }

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

    public int getMin() {
        return min;
    }
}
4 ms (99.2%), Space: 46.7 MB (93.82%) - LeetHub

회고:

Stack 하나에 min값을 같은 Integer 값으로 저장하는 것이 공간복잡도에 있어서 미세하게 더 나은 성능을 보여줬는데, 아마 min값 변경이 있는 경우에만 min값을 push, pop하는 부분에서 차이가 나지 않았나 싶다.