이 글에서는 push, pop, top 연산과 함께 최솟값 조회(getMin)까지 모두 상수 시간 O(1)에 수행할 수 있는 스택을 파이썬으로 구현하는 방법을 알아봅니다. 일반적인 스택은 push, pop, top 연산은 빠르지만, 최솟값을 찾으려면 전체를 순회해야 하는 O(n)의 비용이 듭니다. 이 문제를 해결하는 핵심 아이디어는 이전 최솟값을 스택 자체에 함께 저장하는 것입니다.
알고리즘 설계
구현해야 할 네 가지 연산은 다음과 같습니다.
push(x): 요소 x를 스택에 삽입pop(): 스택의 최상단 요소 제거top(): 스택의 최상단 요소 반환getMin(): 스택 내 최솟값 반환
동작 단계
- 초기화: 스택을 생성하고 최솟값(min)을 무한대(infinity)로 설정합니다.
- push(x) 연산:
- x가 현재 min보다 작거나 같으면, 기존 min을 스택에 먼저 저장한 후 min := x로 갱신합니다.
- x를 스택에 push합니다.
- pop() 연산:
- 최상단 요소를 t에 저장한 뒤 스택에서 제거합니다.
- t가 현재 min이라면, 그다음 요소(저장해 둔 이전 min)를 꺼내 min을 복원합니다.
- top() 연산: 최상단 요소를 그대로 반환합니다.
- getMin() 연산: 저장된 min 값을 반환합니다.
구현 예제
아래 코드는 위 알고리즘을 파이썬 클래스로 구현한 것입니다. push 시 이전 최솟값을 스택에 함께 쌓는 방식으로, pop할 때 최솟값을 되돌릴 수 있습니다.
class MinStack(object):
def __init__(self):
self.min = float('inf')
self.stack = []
def push(self, x):
if x <= self.min:
self.stack.append(self.min) # 이전 최솟값 백업
self.min = x
self.stack.append(x)
def pop(self):
t = self.stack[-1]
self.stack.pop()
if self.min == t: # 최솟값이 제거된 경우
self.min = self.stack[-1] # 백업해 둔 값으로 복원
self.stack.pop()
def top(self):
return self.stack[-1]
def getMin(self):
return self.min
m = MinStack()
m.push(-2)
m.push(0)
m.push(-3)
print(m.getMin()) # -3
m.pop()
print(m.top()) # 0
print(m.getMin()) # -2실행 결과
-3 0 -2
동작 과정 살펴보기
- -2, 0, -3을 차례로 push하면, -3이 새로운 최솟값이 되므로 getMin()은 -3을 반환합니다.
- pop()으로 -3이 제거되면, 스택에는 백업해 둔 이전 최솟값(-2)이 남아 있어 min이 자동으로 복원됩니다.
- 이제 top()은 0, getMin()은 -2를 반환합니다.
시간 및 공간 복잡도
- 시간 복잡도: 모든 연산(push, pop, top, getMin)이 O(1)입니다.
- 공간 복잡도: 최악의 경우(내림차순으로 push) 각 요소마다 이전 최솟값이 추가로 저장되므로 O(n)입니다.
이처럼 이전 최솟값을 스택에 함께 저장하는 기법만으로, 별도의 보조 스택 없이도 모든 연산을 상수 시간에 처리하는 최소 스택을 손쉽게 구현할 수 있습니다.