[LeetCode] 155. Min Stack (Python)

https://leetcode.com/

1. 문제

• 문제 링크 : 155. Min Stack
• 문제 태크 : Stack

---

2. 문제 설명

Implement the MinStack class → MinStack의 클래스를 구현해야한다.

• MinStack() initializes the stack object.
  → 스택으로 사용할 객체 생성하기
  → Python에서는 List를 사용하여 스택처럼 작업 수행
• void push(int val) pushes the element val onto the stack.
  → 스택에 값을 넣기
• void pop() removes the element on the top of the stack.
  → 가장 최근에 넣었던 값 제거하기
  → 스택에 1개 이상의 값이 존재할 경우에만 가능
• int top() gets the top element of the stack.
  → 가장 최근에 넣은 값 보여주기
  → 스택에 1개 이상의 값이 존재할 경우에만 가능
• int getMin() retrieves the minimum element in the stack.
  → 스택의 요소 중 가장 작은 값 보여주기
  → 스택에 1개 이상의 값이 존재할 경우에만 가능

---

3. 문제 풀이

여기서 중요한 것은 모든 작업은 O(1)의 시간 복잡도를 가져야한다.

즉, 어떻게 스택 내의 최솟값이 무엇인지 알아내야 한다.

아래의 그림과 같이 (현재값, 당시 최솟값)을 요소로 가지는 스택으로 구현했다.

이렇게 구현하면 stack[-1][1]의 값은 항상 현재 스택 내의 최솟값을 나타낸다.

그러면 다른 작업 없이 최솟값을 구할 수 있으므로 O(1)의 조건을 만족한다.

---

4. 코드

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

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

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

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

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