[LeetCode] 155. Min Stack - Java[자바]

링크

문제

push, pop, top, 최소 요소 검색을 상수 시간 소요하는 스택을 설계하세요.

MinStack 클래스를 구현합니다:

• 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.

풀이

class MinStack {  
  
  
    public MinStack() {  
  
    }  
  
    public void push(int val) {  
  
    }  
  
    public void pop() {  
  
    }  
  
    public int top() {  
  
    }  
  
    public int getMin() {  
  
    }  
}  
  
/**  
 * Your MinStack object will be instantiated and called as such: 
 * MinStack obj = new MinStack(); 
 * obj.push(val); 
 * obj.pop(); 
 * int param_3 = obj.top(); 
 * int param_4 = obj.getMin(); 
*/

위와 같이 기본 template이 주어진다.

• 두개의 ArrayList를 선언해서, 한 개에는 모든 값들을 저장한다.
• 다른 한개에는 최솟값들을 저장한다.
  - List가 비어있거나, 마지막으로 저장된 값(리스트의 최솟값)보다 작은 값이면 저장한다.
• pop을 하는 경우, 모든 값을 저장한 list에서는 그냥 remove를 한다.
  - 최솟값을 저장한 list에서는 방금 제거한 값이 최솟값인 경우에 삭제한다

import java.util.*;  
  
class MinStack {  
  
    List<Integer> stack;  
    List<Integer> minStack;  
  
  
    public MinStack() {  
        stack = new ArrayList<>();  
        minStack = new ArrayList<>();  
    }  
  
    public void push(int val) {  
        stack.add(val);  
        if (minStack.isEmpty() || val <= minStack.get(minStack.size() - 1)) {  
            minStack.add(val);  
        }  
    }  
  
    public void pop() {  
        int val = stack.remove(stack.size() - 1);  
        if (val == minStack.get(minStack.size() - 1)) {  
            minStack.remove(minStack.size() - 1);  
        }  
    }  
  
    public int top() {  
        return stack.get(stack.size() - 1);  
    }  
  
    public int getMin() {  
        return minStack.get(minStack.size() - 1);  
    }  
}

위와 같이 해결할 수 있다.

Stack을 구현하라고 한 문제라 Stack을 사용하면 안될 것 같았는데, List대신 그냥 Stack 두개를 동일하게 선언해도 문제가 풀린다.. 이건 뭔지 모르겠다..