LeetCode 155 Min Stack 풀이: 보조 스택으로 최솟값 O(1) 조회
작성·코드 검증: solve together · 작성 언어: Python
0. 문제 링크와 출처
- 문제: 155. Min Stack
- 출처: LeetCode
- 자체 판단 난이도: Level 3
일반적인 스택의 동작에 현재 최솟값을 반환하는 기능을 추가해야 한다. 최솟값을 매번
전체 스택에서 검색하면 getMin()이 O(n)이 되므로, 자료구조의 상태를 추가로 설계해야
한다. 값 스택과 보조 스택을 동기화하는 방법과 중복 최솟값 처리가 필요하므로 Level 3으로
판단했다.
1. 문제 요약
스택을 다음 네 가지 연산을 지원하도록 설계해야 한다.
push(val):val을 스택의 맨 위에 추가한다.pop(): 맨 위 원소를 제거한다.top(): 맨 위 원소를 반환한다.getMin(): 현재 스택에 들어 있는 값 중 최솟값을 반환한다.
모든 연산은 O(1) 시간에 수행해야 한다. pop, top, getMin은 비어 있지 않은
스택에서만 호출되며, 전체 연산 호출 횟수는 최대 3 * 10^4다. 값의 범위는
-2^31 이상 2^31 - 1 이하다.
예를 들어 -2, 0, -3을 순서대로 넣으면 최솟값은 -3이다. 이후 -3을 제거하면
스택의 최솟값은 다시 -2가 된다. 제거된 최솟값을 빠르게 복원할 수 있어야 한다.
2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명
상태 전이와 보조 스택
스택의 맨 위 원소는 리스트의 마지막 원소이므로 O(1)에 확인할 수 있다. 하지만
최솟값은 스택 중간에 있을 수 있어 일반 스택만으로는 바로 알 수 없다.
그래서 다음 두 스택을 같은 길이로 유지한다.
stack: 실제로 삽입된 모든 값을 저장한다.min_stack: 각 깊이까지의 최솟값을 저장한다.
min_stack의 i번째 원소는 stack의 i번째 원소까지 고려했을 때의 최솟값이다.
새 값 val을 넣을 때는 이전 최솟값과 비교해 다음 상태를 만든다.
min_stack의 새 원소 = min(val, min_stack의 현재 top)이렇게 하면 min_stack의 top은 항상 현재 stack 전체의 최솟값이다. pop()할 때 두
스택에서 함께 하나씩 제거하면, 제거된 값이 최솟값이었더라도 이전 깊이의 최솟값이 즉시
min_stack의 top으로 복원된다.
보조 스택으로 최솟값을 연산과 동기화하기
이 문제에서는 최솟값 하나만 저장하면 충분하지 않다. 현재 최솟값을 제거한 뒤 필요한 이전 최솟값도 알아야 하기 때문이다. 각 스택 깊이의 최솟값을 모두 기록하면 이 정보를 스택 구조 안에 보존할 수 있다.
최솟값과 같은 값이 여러 번 들어올 수 있으므로, 새로운 값이 현재 최솟값과 같을 때도
min_stack에 기록해야 한다. 모든 push에서 값을 기록하면 두 스택의 길이가 항상 같아져
pop의 동기화가 단순하고 안전하다.
시간·공간 복잡도
각 메서드는 리스트의 끝에서 한 번만 삽입, 삭제 또는 조회하므로 시간 복잡도는 모두 O(1)이다.
두 스택에 최대 n개의 원소를 저장하므로 공간 복잡도는 O(n)이다.
오답 접근과 반례
일반 스택만 저장하고 getMin()을 호출할 때마다 모든 원소를 순회하면 최솟값은 구할 수
있지만, getMin()의 시간 복잡도가 O(n)이 된다. 예를 들어 원소가 1부터 30000까지
많이 쌓인 상태에서 getMin()을 반복 호출하면 문제의 O(1) 조건을 만족하지 못한다.
반대로 min_stack에 새로운 최솟값이 될 때만 값을 넣는 방식은 중복 값을 놓치기 쉽다.
다음과 같이 최솟값 2가 두 번 들어온 경우를 생각할 수 있다.
push(2), push(2), pop(), getMin()두 번째 2를 보조 스택에 기록하지 않았다면 첫 번째 2를 제거한 시점에 보조 스택이
비게 되어 잘못된 결과를 반환할 수 있다. 이 글의 구현은 같은 최솟값도 매번 기록해
이 문제를 피한다.
3. 문제 해결 코드 (Python)
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, val: int) -> None:
self.stack.append(val)
if self.min_stack:
val = min(val, self.min_stack[-1])
self.min_stack.append(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]push에서는 실제 값을 stack에 먼저 저장하고, 현재 최솟값과 비교한 결과를
min_stack에 저장한다. 첫 번째 원소를 넣을 때는 비교할 이전 최솟값이 없으므로 그 값
자체가 최솟값이다.
pop에서는 두 스택을 함께 제거한다. 두 스택의 길이와 각 깊이의 의미가 항상 일치하므로,
현재 최솟값이 제거되는 경우에도 바로 이전 깊이의 최솟값을 복원할 수 있다.
복사해 실행할 테스트
아래 검사를 풀이 코드 아래에 붙여 python 파일명.py로 실행하면 최솟값의 갱신·복원과 중복 최솟값 처리를 확인할 수 있다.
stack = MinStack()
stack.push(-2)
stack.push(0)
stack.push(-3)
assert stack.getMin() == -3
stack.pop()
assert stack.top() == 0
assert stack.getMin() == -2
stack = MinStack()
stack.push(2)
stack.push(2)
stack.pop()
assert stack.getMin() == 24. 공식 예제와 추가 검증
공식 예제와 중복 최솟값, 정수 범위 경계값을 Python 코드로 실행해 확인했다.
공식 예제
입력: push(-2), push(0), push(-3), getMin(), pop(), top(), getMin()
기대 출력: [null, null, null, -3, null, 0, -2]
확인 결과: 통과
검증 목적: 최솟값 제거 후 이전 최솟값이 복원되는지 확인추가 검증 1: 중복된 최솟값
입력: push(2), push(2), getMin(), pop(), getMin()
기대 출력: [null, null, 2, null, 2]
확인 결과: 통과
검증 목적: 같은 최솟값을 두 번 저장하고 하나를 제거해도 최솟값을 유지하는지 확인추가 검증 2: 허용된 정수 범위의 양끝값
입력: push(2147483647), getMin(), push(-2147483648), top(), getMin(), pop(), getMin()
기대 출력: [null, 2147483647, null, -2147483648, -2147483648, null, 2147483647]
확인 결과: 통과
검증 목적: 문제에서 허용하는 최댓값과 최솟값을 처리하는지 확인5. 다른 풀이 방식 검색 및 비교
- LeetCode 공식 문제는 네 가지 스택
연산과 각 연산의
O(1)시간 조건을 정의한다. - NeetCode의 Min Stack 설명은 일반 스택과 별도로 현재까지의 최솟값을 보조 스택에 기록하는 접근과, 값을 인코딩해 하나의 스택으로 처리하는 접근을 비교한다.
보조 스택을 사용하는 방식은 최솟값을 각 깊이에 기록하므로 구현과 불변식이 직관적이다. 하나의 스택에 차이값을 인코딩하는 방식은 추가 스택을 줄일 수 있지만, 최솟값 변경 여부를 판별하고 이전 최솟값을 복원하는 식을 별도로 관리해야 한다. 언어에 따라 정수 오버플로를 주의해야 하므로, 이 문제에서는 두 스택을 사용하는 풀이를 선택했다.
마무리
Min Stack은 기존 자료구조의 동작을 유지하면서 특정 질의를 빠르게 만들기 위해 보조 상태를
함께 저장하는 문제다. 실제 값 스택과 각 깊이의 최솟값을 기록한 보조 스택을 동기화하면
push, pop, top, getMin을 모두 O(1)에 처리할 수 있다. 같은 최솟값도 각각
기록해야 pop 이후의 상태를 정확하게 복원할 수 있다는 점이 핵심이다.