30-Day LeetCoding Challenge - 10Day (Min Stack)

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.

• Stack을 구현해야 하는 문제이다.
  push(x), pop(), top(), getMin() 메소드도 함께 구현해야한다.

Solution

import java.util.*;
class MinStack {

    /** initialize your data structure here. */
	List<Integer> stack;
    
	public MinStack() {
		stack = new ArrayList<Integer>();
	}
    
	public void push(int x) {
		stack.add(0, x);
	}
	
	public void pop() {
		stack.remove(0);
	}

	public int top() {
		return stack.get(0);	
	}

	public int getMin() {
		int min = Integer.MAX_VALUE;
		for (int i = 0; i < stack.size(); i++) {
			if (min > stack.get(i)) {
				min = stack.get(i);
			}
		}
		return min;
	}
}

• 문제에서 요구하는 MinStack을 ArrayList를 이용해 구현해 보았다.
• MinStack 인스턴스를 생성하면 객체 할당이 된다.
• push(int x)는 항상 ArrayList의 첫 번째 index로 삽입
• Stack은 Last In First Out 이니 나중에 들어온 값이 첫 번째로 나가야한다.
  stack은 항상 첫 번째 요소로 삽입되니 마지막에 들어온 값은 항상 index가 0이다.
  그러므로 pop()은 항상 stack의 0번째 index를 삭제한다.
• top()은 스택의 마지막에 들어온 값을 출력하는 메소드이다.
• getMin()은 stack의 최솟값을 반환해주는 메소드이다.
  나는 stack의 0번째 index부터 마지막 index까지 최솟값을 찾아서 반환해주게 작성하였다.

마침

문제를 풀고 다른 사람들이 작성한 코드를 보았는데 push()메소드를 작성할 때 값이 들어올 때 부터 최솟값을 비교하면서 최솟값을 가지고 있는 변수를 따로 생성해서 저장해놓으면 getMin()메소드에서 해당 변수를 바로 반환해주게 하는 방법도 있다는 것을 알았다!