"내일은 반팔 입어도 될까?"
날씨 앱을 만든다고 해봅시다. 사용자가 가장 궁금해하는 건 의외로 단순합니다. "오늘보다 더 더운 날이 언제 와?"
앞으로 며칠간의 예상 기온이 주어질 때, 각 날짜마다 그 날보다 처음으로 더 더운 날이 며칠 뒤인지 알려주려고 합니다. 더운 날이 끝까지 없으면 0이고요.
예: 기온이
[23, 24, 22, 21, 25, 28, 26]이면 정답은[1, 3, 2, 1, 1, 0, 0].Day 1(24°)은 3일 뒤 Day 4(25°)에 처음으로 더 더워지고, Day 5(28°)는 뒤로 더 더운 날이 없어 0.
가장 먼저 떠오르는 풀이 (그리고 그 한계)
직관적으로는 이렇게 풉니다. 각 날짜마다 오른쪽을 끝까지 훑어서 더 더운 날을 찾는 거죠.
for 각 날 i:
for j = i+1 .. 끝:
if temps[j] > temps[i]: 답 = j - i; break작은 입력에서는 잘 동작합니다. 하지만 날짜가 10만 개라면? 10만 × 10만 = 100억 번 비교 → 시간 초과. 이중 반복문의 O(n²)는 코딩테스트에서 자주 발목을 잡습니다.
왜 스택일까? — "기다리는 날들"
여기서 발상을 바꿔봅시다. 각 날짜를 "답을 기다리는 손님" 이라고 생각해 보세요.
- •Day 0 (23°): "언제 나보다 더워지지?" → 아직 모름. 일단 줄(스택)에 서서 대기.
- •Day 1 (24°) 등장: 어?
24 > 23! Day 0의 답을 바로 찾았다. (1일 후) → Day 0는 줄에서 퇴장. - •Day 2 (22°), Day 3 (21°): 점점 추워지니 아무도 답을 못 찾고 줄이 길어집니다.
- •Day 4 (25°) 등장:
25는 줄에서 기다리던21 → 22 → 24를 가까운 순서대로 한 번에 추월! 세 명이 동시에 답을 찾고 퇴장합니다.
눈치채셨나요? 가장 최근에 줄 선 사람이 가장 먼저 빠져나갑니다. 이게 정확히 스택(LIFO) 의 동작이에요.
그리고 줄에 남아 있는 기온들을 보면 항상 내림차순입니다(24 → 22 → 21). 이렇게 *단조성(monotonicity)* 을 유지하는 스택을 단조 스택(Monotonic Stack) 이라고 부릅니다.
핵심은 "한 번 push, 최대 한 번 pop"
단조 스택이 빠른 이유는 명쾌합니다.
- •각 날짜는 스택에 딱 한 번 들어가고(push),
- •더 더운 날을 만나면 최대 한 번 나옵니다(pop).
그러니 전체 연산 횟수가 2n을 넘지 않아요. 곧 O(n). 이중 반복문의 100억 번이 10만 번 수준으로 줄어듭니다.
이 패턴은 "다음으로 더 큰 수", "오른쪽에서 가장 가까운 ~", "주가가 떨어지기 직전" 같은 수많은 변형으로 코딩테스트에 등장합니다. 한 번 원리를 익혀두면 옷만 갈아입은 문제들이 전부 같아 보입니다.
직접 눈으로 확인하기
기온 막대가 늘어서고, 답을 못 찾은 날들이 스택에 쌓이고, 더운 날이 등장하는 순간 연쇄적으로 pop되며 답이 채워지는 전 과정을 단계별 시각화로 준비했습니다. 스택의 변화·정답 배열이 채워지는 모습까지 한눈에 보입니다.