[Stack][Medium] 155. Min Stack

https://leetcode.com/problems/min-stack/description

 

Q. Min 값을 언제나 반환할 수 있는 stack class를 설계하라. 

 이때 모든 함수는 O(1)으로 수행되어야 한다. 

 

Solution. 

 우선 기본 stack 작동을 해야 하므로, 내부적으로 그냥 stack을 하나 가진다. 

 그리고 min 값을 위한 자료구조를 하나 더 두는데, 역시 stack으로 둔다. 

 이 min stack이 비었거나, top 보다 같거나 작으면 이 stack에 값을 채운다. 즉, 적은 값들이 계속 top으로 가게 끔 값을 채운다. => 여기서 큰 값들은 관심이 없으므로, min stack에 저장할 필요가 없다. 

 getMin 할 때, 이 min stack에서 하나씩 peek해서 주면 된다. 

 

 다만 일반 pop() 함수에서 min stack값이 제거 될 수 있으므로, 이를 체크한다. 

 이때 pop()에서 min stack의 top이 아닌 다른 값이 삭제되면 문제가 되는데, 

 이 경우가 되려면 제거되는 값이 min stack의 top보다 큰 값, 즉, 최소값이 아니어야 한다. 

 하지만, min stack의 min 값보다 늦게 push 되면서 min stack의 top보다 큰 값은 min stack에 저장하지 않는다. 

 따라서 이 경우는 발생하지 않는다. 

 

 로직을 코드로 만든다. 

 

 

class MinStack {

    // 항상 min 값을 반환가능한 min stack의 함수들을 구현하라.
    // 이때 모든 함수는 O(1) 시간복잡도에 수행되어야 한다.
    //
    Stack<int> mStack, mMinStack;
    public MinStack() {
        mStack = new Stack<int>();
        mMinStack = new Stack<int>();
    }    
    public void Push(int val) 
    {
        mStack.Push(val);
        if(mMinStack.Count==0 || mMinStack.Peek()>=val)
            mMinStack.Push(val);
    }
    public void Pop() 
    {
        int val = mStack.Pop();
        if(mMinStack.Count>0 && val==mMinStack.Peek())
            mMinStack.Pop();
    }
    public int Top() 
    {
        return mStack.Peek();
    }
    public int GetMin() 
    {
        return mMinStack.Count==0 ? 0 : mMinStack.Peek();
    }
}

 

 

적절한 결과를 얻었다.