← 전체 회차
A-022● Day 222026.05.27mediumleetcode #155neetcode150

최소값 스택

#stack#design
↗ leetcode #155 · min-stack
01

문제

· problem
P.022

최소값 스택

↗ leetcode #155

스택이 푸시, 팝, 탑, 그리고 최소 원소를 상수 시간에 검색하는 기능을 지원하도록 설계하세요. MinStack 클래스를 구현하세요: - MinStack()은 스택 객체를 초기화합니다. - void push(int val)은 요소 val을 스택에 추가합니다. - void pop()은 스택의 맨 위 요소를 제거합니다. - int top()은 스택의 맨 위 요소를 반환합니다. - int getMin()은 스택의 최소 원소를 검색합니다. 모든 함수의 시간 복잡도가 O(1)이어야 합니다.

제약
  • · -2³¹ ≤ val ≤ 2³¹ - 1
  • · pop(), top(), and getMin() are always called on non-empty stacks
  • · At most 3 × 10⁴ total calls to push, pop, top, and getMin
// 지문은 본인 언어 요약 — 원문은 위 링크에서
입출력 예시
example 1input → output
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
[null, null, null, null, -3, null, 0, -2]
02

사전 사고

· pre-solve
● 1리스트 출력→● 2선택→● 3정답 공개
  • ☐
    모든 메서드가 정말 O(1)이어야 하나요?
  • ☐
    최소값을 구할 때마다 스택 전체를 스캔하면 안 되나요?
  • ☐
    새로운 값이 현재 최소값보다 작으면, 그것이 새로운 최소값이 되나요?
  • ☐
    최소값 추적용으로 힙을 사용할 수 있나요?
  • ☐
    최소값 요소를 pop()할 때, 이전 최소값이 자동으로 복구되나요?
  • ☐
    getMin()이 스택에서 원소를 제거해야 하나요?
  • ☐
    스택과 최소값을 추적하는 데 하나의 정수 변수만 충분한가요?
던질 질문에 체크하고 확인을 누르세요
// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)
03

논리 구조

· logic
● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개
// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.
step 1· 데이터 구조 초기화
○
self.stack = []
○
self.stack = {}
○
self.min = float('inf')
step 2· Push: 값을 메인 스택에 추가│ 중첩
○
self.stack.append(val)
○
self.stack.insert(0, val)
step 3· Push: 이 레벨의 최소값 계산│ 중첩
○
val = min(val, self.minStack[-1] if self.minStack else val)
○
val = min(self.stack)
○
val = val
step 4· Push: 최소값을 보조 스택에 저장│ 중첩
○
self.minStack.append(val)
○
self.minStack.insert(0, val)
step 5· Pop: 두 스택 모두에서 제거│ 중첩
○
self.stack.pop()
○
self.stack.pop()
step 6· Top: 맨 위 원소 반환│ 중첩
○
return self.stack[-1]
○
return self.minStack[-1]
step 7· GetMin: O(1)에서 최소값 반환│ 중첩
○
return self.minStack[-1]
○
return min(self.stack)
각 슬롯에 한 줄씩 골라보세요
// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.
04

문제풀이 · 트레이스

· solve
solution.py
1
class MinStack:
2
    def __init__(self):
3
        self.stack = []
4
        self.minStack = []
5
6
    def push(self, val: int) -> None:
7
        self.stack.append(val)
8
        val = min(val, self.minStack[-1] if self.minStack else val)
9
        self.minStack.append(val)
10
11
    def pop(self) -> None:
12
        self.stack.pop()
13
        self.minStack.pop()
14
15
    def top(self) -> int:
16
        return self.stack[-1]
17
18
    def getMin(self) -> int:
19
        return self.minStack[-1]
머릿속 dry-run 케이스
// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.
case 1
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
→
[null, null, null, null, -3, null, 0, -2]
// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.