(leetcode 문제 풀이) Min Stack

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

Implement the MinStack class:
1. MinStack() initializes the stack object.
2. void push(val) pushes the element val onto the stack.
3. void pop() removes the element on the top of the stack.
4. int top() gets the top element of the stack.
5. int getMin() retrieves the minimum element in the stack.

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

# 1차 작성 코드
class MinStack:
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.__stack = []

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

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

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

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

사실상 스택을 구현하는 단순한 문제지만, getMin() 이라는 기능을 어떻게 구현할지 고민했었다. 처음에는 단순하게 min() 을 통해 최솟값을 찾아내면 된다는 생각으로 접근했는데, 시간이 600ms가 걸렸다.

아래는 다른 사람의 코드를 참고한 것인데 아예 별도로 변수를 선언해서 최솟값만 추가되도록 했다. 원소가 추가될 때마다 값을 비교해서 그런지 시간은 52ms밖에 걸리지 않았다.

# 모범 참고 코드
class MinStack:
    def __init__(self):
        self.A = []
        self.M = []
    def push(self, x):
        self.A.append(x)
        M = self.M
        if not M:
            M.append(x)
        else:
            M.append(min(x, M[-1]))
        
    def pop(self):
        self.A.pop()
        self.M.pop()
        
    def top(self):
        return self.A[-1]
    
    def getMin(self):
        return self.M[-1]