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 minineetcode에서 브루트포스로 제공한 코드인데, 이렇게 푸는 사람이 있을까 싶지만?
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)이다.
