[LeetCode | Python] 155. Min Stack

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.

언뜻 보면 간단하게 리스트 하나로 바로 구현하면 될 것 같지만,

모든 메서드가 O(1) time complexity를 가지기 위해서는 생각을 해야하는 문제였다.

 

 

파이썬 클래스와 self

지금까지의 코테 문제를 풀면서는 self를 생각할 필요가 없었는데,

이 문제에서는 클래스와 self를 이해하고 사용해야 풀 수 있었다.

 

클래스 내에 정의된 함수를 '메서드'라고 하며,

self는 클래스 안의 메서드들이 해당 클래스의 인스턴스(객체)에 접근할 수 있도록 해주는 예약어이다.

 

 

풀이 1: 브루트 포스 - getMin에서 O(n)

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:
        tmp = sorted(self.stack)
        return tmp[0]

stack으로 사용할 리스트를 하나 만들면, push pop top은 기본 리스트 메서드들을 사용하여 쉽게 구현할 수 있다.

문제는 getMin인데, 

sorted()나 list.sort() 메서드를 사용하면 둘다 시간복잡도가 O(n log n)이기 때문에 문제의 조건을 만족하지 못한다.

(리트코드에 제출했을 때 통과하긴 했다.)

 

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

더 간단하게 sort를 안 하고 바로 min 메서드를 사용해도 되는데, 

min(self.stack)의 복잡도는 O(n)이다.

(마찬가지로 통과하긴 했다)

 

    def getMin(self) -> int:
        tmp = []
        mini = self.stack[-1]

        while len(self.stack):
            mini = min(mini, self.stack[-1])
            tmp.append(self.stack.pop())
        
        while len(tmp):
            self.stack.append(tmp.pop())
        
        return mini

neetcode에서 브루트포스로 제공한 코드인데, 이렇게 푸는 사람이 있을까 싶지만?

mini를 계속 업데이트하면서 푸는 코드이고 O(n)이 걸린다.

 

브루트포스로 풀어도 통과는 하지만.. 굉장히 오래걸리는 것을 볼 수 있다.

 

 

풀이 2: Two Stacks - 모두 O(1)

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

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

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

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

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

처음부터 stack과 minStack 두 개로 초기화하면, O(1)으로 모든 메서드들을 구현할 수 있다.

이 풀이에서 가장 핵심이 되는 부분은 push 메서드다.

 

val = min(val, self.minStack[-1] if self.minStack else val)

minStack이 비지 않았을 때 minStack의 값과 비교하여 마지막에 추가할 값을 결정하며, 

결과적으로 minStack의 맨 마지막 값에는 항상 최솟값이 추가되게 된다.

이를 활용하여 getMin에서는 minStack의 마지막값을 리턴해주면 된다.

 

여기서 min은 두 값을 비교하므로 시간 복잡도는 O(1)이다.

 

훨씬 빠르다.