Ch.4 스택과 큐

면접 실전: 스택/큐 핵심 문제

Min Stack, Sliding Window Maximum 등 면접 빈출 문제를 해결한다스택/큐/덱을 적재적소에 선택하는 판단력을 기른다

이 세 문제를 풀면 스택/큐 면접은 자신감이 생깁니다

Min Stack, Daily Temperatures, Sliding Window Maximum — 빅테크 면접에서 가장 자주 등장하는 3대 스택/큐 문제를 정복합니다.

O(1)에 최솟값을 알려주는 스택? 윈도우가 움직이면서 최댓값을 O(1)에?

보조 스택, Monotonic Stack, Monotonic Deque — 세 가지 패턴이면 충분합니다.

article

핵심 내용

push, pop, top에 더해 getMin()도 O(1)인 스택을 설계하세요

아이디어: 보조 스택에 각 시점의 최솟값을 함께 기록합니다

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []  # 보조 스택
    
    def push(self, val):
        self.stack.append(val)
        # 현재 최솟값 갱신
        min_val = min(val, self.min_stack[-1] if self.min_stack else val)
        self.min_stack.append(min_val)
    
    def pop(self):
        self.stack.pop()
        self.min_stack.pop()
    
    def top(self):
        return self.stack[-1]
    
    def getMin(self):
        return self.min_stack[-1]

Min Stack 핵심 보조 스택(min_stack)에 '그 시점까지의 최솟값'을 기록 → getMin()은 min_stack[-1] 반환 = O(1) 공간: O(n) — 보조 스택 때문

앞서 배운 Monotonic Stack 패턴의 대표 문제를 다시 정리합니다

def dailyTemperatures(temps):
    n = len(temps)
    answer = [0] * n
    stack = []  # 단조 감소 스택 (인덱스)
    
    for i in range(n):
        while stack and temps[i] > temps[stack[-1]]:
            prev = stack.pop()
            answer[prev] = i - prev
        stack.append(i)
    
    return answer

크기 k인 슬라이딩 윈도우의 최댓값을 O(n)에 구하세요

입력: nums = [1,3,-1,-3,5,3,6,7], k = 3 출력: [3,3,5,5,6,7] 윈도우: [1,3,-1]→3, [3,-1,-3]→3, [-1,-3,5]→5, ...

핵심: Monotonic Deque (단조 감소 덱) 덱에 '후보'만 남기면 됩니다

from collections import deque

def maxSlidingWindow(nums, k):
    dq = deque()  # 인덱스 저장, 단조 감소
    result = []
    
    for i in range(len(nums)):
        # 윈도우 밖 원소 제거
        while dq and dq[0] < i - k + 1:
            dq.popleft()
        # 현재보다 작은 원소는 후보에서 탈락
        while dq and nums[dq[-1]] <= nums[i]:
            dq.pop()
        dq.append(i)
        # 윈도우 완성 후 최댓값 기록
        if i >= k - 1:
            result.append(nums[dq[0]])
    
    return result

print(maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3))
# [3, 3, 5, 5, 6, 7]

시간: O(n) — 각 원소 최대 1회 push + 1회 pop 공간: O(k) — 덱 크기 최대 k

세 문제의 공통점 보조 자료구조로 O(1) 조회를 달성합니다

Min Stack에서 getMin()이 O(1)인 이유는?

Sliding Window Maximum에서 사용하는 자료구조는?

Sliding Window Maximum의 시간복잡도는 O(nk)이다

면접 실전 준비 완료!

key

핵심 용어

1️⃣

스택에 뭘 넣나

인덱스를 넣어서 거리 계산 가능하게

2️⃣

언제 pop하나

현재 온도 > 스택 top 온도일 때

3️⃣

왜 O(n)인가

각 원소 최대 1회 push + 1회 pop

🗑️

popleft

윈도우 밖으로 벗어난 인덱스 제거

💪

pop (뒤)

현재 값보다 작은 후보 탈락

🏆

dq[0]

항상 윈도우 내 최댓값의 인덱스

📊

Min Stack

보조 스택 → getMin() O(1)

🌡️

Daily Temperatures

Monotonic Stack → Next Greater O(n)

🪟

Sliding Window Max

Monotonic Deque → 윈도우 최대 O(n)

edit_note

정리 노트

면접 실전: 스택/큐 핵심 문제

3대 면접 문제

Min Stack: 보조 스택으로 getMin() O(1)
Daily Temperatures: Monotonic Stack → O(n)
Sliding Window Max: Monotonic Deque → O(n)

자료구조 선택 기준

LIFO 필요: 스택 (list)
FIFO 필요: 큐 (deque)
양쪽 연산: 덱 (deque)
최솟/최댓값: 힙 (heapq)

★

면접에서 '왜 이 자료구조를 선택했는지' 설명하는 것이 정답만큼 중요합니다!

check_circle

핵심 정리

1Min Stack — 보조 스택 패턴
2Daily Temperatures — Monotonic Stack 패턴
3Sliding Window Max — Monotonic Deque 패턴

퀴즈와 인터랙션으로 더 깊이 학습하세요

play_circle인터랙티브 레슨 시작