[Leetcode] Min Stack

155. Min Stack

 

문제 요약:

push(), pop(), top(), getMin()을 지원하는 스택을 디자인하라. getMin()은 스택 내 최소 원소를 반환하며 상수 시간에 완료되어야 한다.

 

생각 1:

getMin()을 상수 시간에 하는 것이 포인트. push() 할 때마다 min을 업데이트 하는 것은 어렵지 않지만, min이 pop() 될 경우 직전의 min 값으로 roll back 해야한다. 하지만 직전의 min 값을 다 저장해둘 수가 없으므로 (벡터를 이용해 저장해둘 수는 있겠지만 의미가 없다고 생각했음) 그냥 벡터 하나와 셋 하나를 이용해 해결해야겠다고 생각했다.

 

생각 2:

벡터 하나와 셋 하나를 모두 쓰는 게 비효율적이라는 생각이 들어서 아래와 같은 struct Node를 만들고 set<Node>를 만들어 해결해야겠다고 생각했다.

struct Node {
    int val;
    Node* prev;
};

 

대박적인 풀이 발견: leetcode.com/problems/min-stack/discuss/647178/CPP-with-one-stacklessintgreater

push() 할 때 min이 업데이트된다면 직전의 min을 먼저 push한다. 스택을 원소 저장 용도로만 쓰는 게 아니라, 직전의 min 이라는 다른 정보를 저장하는 용도로도 동시에 사용하는 것이다. 그러면 현재의 min이 pop() 되더라도 push 해두었던 직전의 min으로 min을 roll back 할 수 있다. 결과적으로 벡터 하나만 사용했으며 원소를 모두 traverse 하는 코드도 없다.

class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {
        
    }
    
    void push(int x) {
        if(x <= min){
            v.emplace_back(min);
            min = x;
        }
        v.emplace_back(x);
    }
    
    void pop() {
        if(top() == min){
            v.pop_back();
            min = v.back();
        }
        v.pop_back();
    }
    
    int top() {
        return v.back();
    }
    
    int getMin() {
        return min;
    }
    
private:
    vector<int> v;
    int min = INT_MAX;
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(x);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */