문제

https://leetcode.com/problems/min-stack/description/?envType=study-plan-v2&envId=top-interview-150

해결 방법

• 일반적인 Stack이라고 생각해보면 ArrayList로 구현 가능함
  - push() : 맨 뒤에 값 삽입
  • pop() : 맨 뒤에 값 삭제
  • top() : 맨 뒤에 값 return
  • 모두 O(1)의 시간에 해결 가능
• 여기서 문제는 getMin() 메소드가 추가되는데, 이는 현재 Stack에서 가장 작은 값을 return 해야 한다는 것 => Stack의 모든 값을 순회한다면 O(n)의 시간복잡도가 걸림
• 이를 해결하기 위해 아래의 상황을 가정해보자
  1. Stack에 {2, 3}이 들어간 상황
  • 뒤의 값 3을 삭제해도 Stack의 min 값에는 영향이 없음 => 3은 의미 없는 숫자로 판단
  2. Stack에 {3, 2}가 들어간 상황
  • 뒤의 값 2를 삭제하면 Stack의 min 값이 2에서 3으로 바뀜
• 기존의 Stack과 별도로 minStack을 생성 후 x라는 값이 삽입될 때
  • x가 기존의 min값보다 크다면 getMin() 메소드에서는 아무 의미 없는 값으로 판단하여 기존의 min값 삽입
  • x가 min값보다 작다면 minStack에는 x값 삽입 및 min 값 갱신
  • getMin() 메소드 호출 시, minStack의 마지막 값 return

코드

class MinStack {

    List<Integer> stack;
    List<Integer> minStack;
    int minValue;

    public MinStack() {
        stack = new ArrayList<>();
        minStack = new ArrayList<>();
        minValue = Integer.MAX_VALUE;
    }
    
    public void push(int val) {
        if (val < minValue) {
            minValue = val;
        }

        stack.add(val);
        minStack.add(minValue);
    }
    
    public void pop() {
        stack.remove(stack.size() - 1);

        int temp = minStack.remove(minStack.size() - 1);
        if (temp == minValue) {
            minValue = minStack.isEmpty() ? Integer.MAX_VALUE : getMin();
        }
    }
    
    public int top() {
        return stack.get(stack.size() - 1);
    }
    
    public int getMin() {
        return minStack.get(minStack.size() - 1);
    }
}

결과