leetcode top interview 150 | Min Stack | ArrayList

Question

 

Stack의 push, pop, top, getMin 메소드를 디자인하기

각각의 메소드는 O(1)의 복잡도로 수행되어야한다.

 

• MinStack()스택 개체를 초기화합니다.
• void push(int val)요소를 val스택에 푸시합니다.
• void pop()스택 맨 위에 있는 요소를 제거합니다.
• int top()스택의 최상위 요소를 가져옵니다.
• int getMin()스택에서 최소 요소를 검색합니다.

 

Accepted Code - ArrayList로 Stack 구조 만들기 

import java.util.LinkedList;
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()){// 초깃값 설정 
            minStack.add(val);
        }else if(val < minStack.get(minStack.size() - 1)){
            minStack.add(val);
        }
    }
    
    public void pop() {
        if(!stack.isEmpty()){
            int removeNum = stack.remove(stack.size() - 1);
            if(!stack.contains(removeNum) && minStack.contains(removeNum))
                minStack.remove(minStack.indexOf(removeNum));
        }
    }
    
    public int top() {
        return stack.get(stack.size() - 1);
    }
    
    public int getMin() {
        return minStack.get(minStack.size() - 1);
    }
}

/**
 * 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();
 */

 

Solve

 

배열은 전체 push가 일어날 크기를 알아야 할당이 가능하므로 크기를 몰라도 저장할 수 있는 List로 생각해서 접근했다.

 

Stack 역할을 하는 ArrayList를 하나만 놓고 풀면 getMin() 연산을 할때 최솟값을 검색하면서 O(N)이 수행되므로, ArrayList 하나가 더 필요하다. 그리고 해당 리스트에서 맨 끝에 min값을 저장하도록 해야 바로 O(1)만에 최솟값을 가져올 수 있다. 

 

따라서 push, pop연산을 수행할 리스트 stack과 최솟값을 맨 앞에 저장할 리스트 minStack을 초기화해주고, top 연산은 stack 리스트에 가장 마지막에 저장된 요소를 리턴하도록 해줬다. getMin 연산은 minStack리스트의 가장 마지막에 저장된 요소가 최솟값이니 해당 값을 리턴하도록 해줬다. 

 

push 연산은 stack 리스트에는 연산이 요청될 때마다 add해주면 되고, minStack리스트는 끝에 저장되어있는 가장 작은 value를 가져와 비교 후 작은 값을 갱신해줬다.

 

pop연산은 stack 리스트에서 가장 마지막에 저장된 요소를 remove 해주고, minStack 리스트는 해당 인덱스 위치를 indexOf로 알아내 remove해줬다. 

 

 

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

Min Stack - LeetCode