풀이_LC155.md

🦖 LeetCode 155. Min Stack

• Date : 2021.08.08(일)
• Time : 15분

Problem

• Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
• Implement the MinStack class:

  MinStack() initializes the stack object.
  void push(val) pushes the element val onto the stack.
  void pop() removes the element on the top of the stack.
  int top() gets the top element of the stack.
  int getMin() retrieves the minimum element in the stack.
  

Constraints

• -2^31 <= val <= 2^31 - 1 Methods pop, top and getMin operations will always be called on non-empty stacks. At most 3 * 10^4 calls will be made to push, pop, top, and getMin.

Example

• Input :

  ["MinStack","push","push","push","getMin","pop","top","getMin"]
  [[],[-2],[0],[-3],[],[],[],[]]
  

• Output : [null,null,null,null,-3,null,0,-2]
• Explanation :

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

풀이

class MinStack:

    def __init__(self):
        self.stack = []

    def push(self, val: int) -> None:
        self.stack.append(val)

    def pop(self) -> None:
        self.stack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return min(self.stack)

: 처음 풀이는 그냥 직관적으로 짜 보았다. 여기서 밑의 코드와 다른점은 최소값을 찾을 때 min() 함수를 사용했다는 것이다. 이 코드로는 557 ms의 RunTime이 발생했다.

class MinStack:

    def __init__(self):
        self.stack = []
        self.min = None 

    def push(self, val: int) -> None:
        if self.min is None:
            self.min = val
        else:
            self.min = min(self.min, val)
        self.stack.append(val)

    def pop(self) -> None:
        poppedItem = self.stack.pop()
        if self.min == poppedItem:
            self.min = min(self.stack) if self.stack else None

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.min

: 두번째 풀이는 최소값을 항상 update 시켜주는 방식을 사용했다. self.min의 값이 항상 변경되는 것을 볼 수 있다.
첫번째, push에서는 min이 비어있다면 바로 그 값을 min으로 설정하였고, 비어있지 않다면 둘 중 더 작은 값을 min으로 설정하였다.
두번째, pop에서는 일단 stack의 제일 위에 값을 추출해주었고 그 값이 min과 동일하고, pop했을 때 stack에 아직 값이 남아있다면 다시 그 stack의 최소값을 찾아서 min값을 업데이트 시켜주었다. 하지만 pop으로 인해 stack이 empty상태로 돌아갔다면, min도 None으로 변경시켜주었다.
세번째, top에서는 min과 상관없이, stack의 제일 top값을 return 해주었다. 네번째, getMin에서는 계속 업데이트 시켜준 min의 값을 return 해주면 된다.
이렇게 변경해보니, Runtime이 62ms로 감소했다.