Leet Code - 155. Min Stack(C++)

예제: Min Stack

문제
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

• push(x) -- Push element x onto stack.
• pop() -- Removes the element on top of the stack.
• top() -- Get the top element.
• getMin() -- Retrieve the minimum element in the stack.

Example:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.

풀이

문제를 읽어보면, 결국 getMin() 함수가 있는 stack을 구현하라는건데.. 처음에 필자는 stack을 쓰지 말라는 뜻인가? 하고 vector를 써서 구현하니, 시간이 꽤나 오래걸렸다.
대부분의 시간은 min값을 구하는데 걸렸을 것이 분명하다.

보다 효율적인 방법은 두 개의 stack을 사용하는 것이었다. 필자는 처음에 min값을 어떻게 저장하는지에 대해 한참을 고민했다가 결국 다른 사람들의 풀이를 답습했다.

min값을 최신화 하는 방법은, push로 들어오는 x값과 minStack의 top값을 비교하여 작은값을 계속 저장하면, pop() 함수가 발생해도 index의 변화 없이 안정적으로 변화하는 min값을 저장할 수 있다.

전체적인 소스코드는 아래와 같다.

소스 코드

/* CASE1 */
class MinStack {
private:
	vector<int> minStack;
public:
	/** initialize your data structure here. */
	MinStack() {
	}

	void push(int x) {
		minStack.push_back(x);
	}

	void pop() {
		minStack.erase(minStack.end() - 1);
	}

	int top() {
		return minStack[minStack.size() - 1];
	}

	int getMin() {
		return *min_element(minStack.begin(), minStack.end());
	}
};

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


/* CASE2 */
class MinStack {
private:
	stack<int> st;
	stack<int> minSt;
public:
	/** initialize your data structure here. */
	MinStack() {

	}

	void push(int x) {
		st.push(x);
		minSt.push(minSt.empty() ? x : min(minSt.top(), x));
	}

	void pop() {
		st.pop();
		minSt.pop();
	}

	int top() {
		return st.top();
	}

	int getMin() {
		return minSt.top();
	}
};

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

풀이 후기

다른 사람의 풀이를 너무 쉽게 봐버리는것도 버릇이 되어가는 것 같다. 깊게 생각하고, 또 생각하고 나서 참고용으로 보도록 해야겠다.