Minstack 구현하기 , leet code Min Stack

leetCode 문제를 풀던 중 Min Stack 문제를 만나게 되었다. (https://leetcode.com/problems/min-stack/)

기본 스택과 할 수 있는 기능은 똑같은데 getMin 함수를 통해 min 값을 추출하는 것이 중요하다.

나는 여기서 stack 이 현재 min값과 자신의 값을 둘다 가지고 있으면 해결할 수 있을 것이라 생각했다.

이제 어떻게 풀었는지 보여주겠다.

class MinStack {
public:
    stack<pair<int,int>> st;
    MinStack(){
    }
    void push(int x) {
        int mmin;
        if(st.size() == 0)
            mmin = x;
        else
            mmin = min(st.top().second, x);
        
        st.push({x,mmin});
    }
    
    void pop() {
        st.pop();
    }
    
    int top() {
        return st.top().first;
    }
    
    int getMin() {
        return st.top().second;
    }
};

코드를 보면 push 부분이 가장 중요한 것임을 알 수 있다.

Push 할 때, 현재 top 에서의 min값과 들어오는 값을 비교해서 min 값을 찾는다.

그러면 이제 stack에 push 할 때, 들어온 x 값과 min 값을 함께 넣으면 getMin 함수에서 min 값을 얻으려고 할 때는 top 의 second 를 리턴해주면된다.