LeetCode Top Interview 150) Min Stack

Question

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(int 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.
• You must implement a solution with O(1) time complexity for each function.

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.

class MinStack:

    def __init__(self):

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

    def pop(self) -> None:

    def top(self) -> int:

    def getMin(self) -> int:

---

---

보기와 같이 주어진 MinStack클래스를 조건에 맞춰 완성시키는 문제입니다. 원래라면 빈 메소드나 최대 갯수가 있는 상황에서의 예외처리가 필요하지만, 비어있는 상태에서는 pop, top, getMin 메소드를 호출하지 않으니 예외처리는 할 필요가 없습니다.
그리고 getMin으로 현재 스택에서의 최소값을 시간복잡도 O(1)로 호출하는 구현 사항도 있습니다.

제가 생각한 코드는 다음과 같습니다.

class MinStack:

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

    def push(self, val: int) -> None:
        self.stack.append(val)
        min_val = min(self.min_stack[-1],val) if self.min_stack else val
        self.min_stack.append(min_val)

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

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

    def getMin(self) -> int:
        return self.min_stack[-1]
        

• 클래스는 stack 리스트와 최솟값을 저장하는 min_stack 리스트를 가집니다.
• push 메서드에서는 스택에 값을 넣습니다.
  • min_stack은 매번 스택에 쌓일 때 최솟값을 저장하는 스택입니다. push가 호출될 때 마다 이전까지의 최솟값과 현재값을 비교하여 작은 값을 넣습니다.
• pop 메서드에서는 stack, min_stack 둘 다 요소를 하나씩 제거합니다. 파이썬의 리스트pop은 리턴값이 존재하지만 함수의 리턴값을 None 상태로 정의했으므로 리턴값을 주지는 않습니다.
• top, getMin 메서드에서는 각각 stack의 끝 값, min_stack의 끝 값을 리턴합니다.

---

간단해보이는 알고리즘이지만 최솟값을 저장하는 방식에서 고민을 했습니다. 굳이 또다른 스택이 필요할까라는 생각을 했지만..
매 순간의 최솟값을 알고 있어야만 원소의 추가, 제거를 할 때 마다 최솟값을 알 수 있다는 사실을 생각해낸 후로는 가벼운 마음으로 리스트를 사용했고, 알고리즘 구현에는 큰 어려움이 없었습니다.