HackerRank, 코드시그널, 또는 화상 공유 기반 라이브 코딩 면접에서 시간 제한 안에 풀어야 하는 배열 문제 중 상당수가 "각 원소에 대해, 그것보다 큰(혹은 작은) 다음 원소를 찾으라" 형태로 환원된다. 단순 이중 반복문으로 풀면 O(N²)이 되고, N이 10⁵만 되어도 타임아웃이 난다. 이 때 Monotonic Stack(단조 스택)을 알고 있느...
HackerRank, 코드시그널, 또는 화상 공유 기반 라이브 코딩 면접에서 시간 제한 안에 풀어야 하는 배열 문제 중 상당수가 "각 원소에 대해, 그것보다 큰(혹은 작은) 다음 원소를 찾으라" 형태로 환원된다. 단순 이중 반복문으로 풀면 O(N²)이 되고, N이 10⁵만 되어도 타임아웃이 난다. 이 때 Monotonic Stack(단조 스택)을 알고 있느냐에 따라 30분 안에 풀고 설명까지 마치느냐, 아니면 brute force로 시작했다가 시간에 쫓겨 디버깅하느냐가 갈린다.
시니어 백엔드 면접에서 자료구조 자체를 묻는 비중은 줄지만, 라이브 코딩은 여전히 "이 사람이 자료구조를 도구로 쓸 수 있는가" 를 검증한다. Monotonic Stack은 외워서 풀이를 적는 알고리즘이 아니라 "스택의 단조성을 유지한다"는 한 줄짜리 발상으로 여러 변형 문제를 통일적으로 푸는 패턴이라, 면접관이 follow-up을 던지기에 좋다. 따라서 답을 적는 것보다 "왜 이 자료구조가 이 문제에 맞는지" 설명할 수 있어야 한다.
Monotonic Stack은 이름 그대로 스택 안의 원소가 아래에서 위로 (또는 위에서 아래로) 단조 증가하거나 단조 감소하도록 유지되는 스택이다. 일반 스택과 자료구조는 동일하지만, push 직전에 단조성이 깨질 원소들을 모두 pop 해버리는 규칙이 추가된다.
스택을 단조 감소(top이 작은 값, bottom이 큰 값)로 유지한다고 하자. 새 원소 x를 push 하기 전에, 스택 top이 x보다 작거나 같으면 pop 한다. pop 되는 원소 입장에서 보면 자기보다 큰 첫 번째 원소가 바로 x다. 이렇게 pop 하는 순간 그 원소의 답이 x로 확정된다.
이 발상이 핵심이고, 나머지는 전부 변형이다.
| 문제 변형 | 스택 단조성 | pop 조건 |
|---|---|---|
| 다음으로 큰 원소 (Next Greater) | 감소 | top ≤ 현재값 일 때 pop |
| 다음으로 작은 원소 (Next Smaller) | 증가 | top ≥ 현재값 일 때 pop |
| 이전으로 큰 원소 (Previous Greater) | 감소, 왼→오 진행 | 같음 |
| 히스토그램 최대 직사각형 | 증가 | top ≥ 현재값 일 때 pop, pop 시 면적 계산 |
| 일일 온도 / 주가 스팬 | 감소 | top ≤ 현재값 일 때 pop |
라이브 코딩에서 가장 흔한 첫 실수가 스택에 값(value)을 그대로 넣는 것이다. 단순한 "다음 큰 값" 정도는 값으로도 풀리지만, 거의 모든 변형 문제에서 다음 중 하나가 필요하다.
따라서 라이브 코딩에서 손이 멈출 일을 줄이려면 처음부터 Deque<Integer>에 인덱스를 넣는 것을 기본 패턴으로 굳혀라. 값이 필요하면 arr[stack.peek()]으로 접근하면 된다. 이 한 가지 습관이 N+1 문제처럼 잔버그의 절반을 막는다.
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && arr[stack.peek()] < arr[i]) {
int popped = stack.pop();
result[popped] = arr[i]; // 또는 i - popped 등
}
stack.push(i);
}값 저장 패턴은 "Next Greater Element I"처럼 답을 인덱스 매핑할 필요가 없는 매우 좁은 경우에만 쓰고, 면접에서는 인덱스 저장 한 가지로 통일하는 것이 인지 부담이 적다.
두 번째로 흔한 버그는 pop 조건의 부등호다. <인지 <=인지에 따라 답이 달라진다.
arr[stack.peek()] < arr[i] 일 때 pop. 같은 값을 만나도 pop 하지 않으므로, 같은 값은 자기 답이 될 수 없다.arr[stack.peek()] <= arr[i] 일 때 pop.히스토그램 최대 직사각형에서 같은 높이 막대들이 연속할 때 <=로 처리하느냐 <로 처리하느냐에 따라 너비 계산이 달라지므로, "엄격히 vs 같거나"의 의미를 문제 진술에서 먼저 확인하고 화이트보드에 한 줄 주석으로 박아두는 것이 안전하다.
면접관이 "왜 <=을 썼나요?" 라고 물으면, "같은 값이 들어왔을 때 기존 원소를 pop 시켜서 새 원소가 그 자리의 영역을 흡수하도록 만들기 위해서"처럼 의미 단위로 답할 수 있어야 한다.
면접관이 가장 자주 던지는 follow-up 중 하나가 "왜 O(N)인가? while 안에 또 반복문이 있는데?" 다. 답은 각 인덱스가 스택에 정확히 한 번 push 되고, 최대 한 번 pop 된다는 amortized 분석이다.
내부 while 루프가 한 번에 여러 개를 pop 하더라도, 그 pop 된 원소들은 두 번 다시 스택에 들어가지 않는다. 따라서 전체 push/pop 횟수의 합은 2N을 넘지 않는다. 외부 for 루프 N + 내부 pop 총합 ≤ N = 총 2N → O(N).
이 답을 라이브 코딩에서 시간복잡도를 적기 전에 한 줄 주석으로 적어두는 습관을 들이면, 면접관이 묻기 전에 선제적으로 짚어주는 효과가 있다.
// 각 원소는 최대 1번 push, 1번 pop → amortized O(N)루프가 끝났는데 스택에 아직 원소가 남아 있다면, 그것들은 자기보다 큰(혹은 작은) 다음 원소가 영원히 등장하지 않은 원소들이다. 문제에 따라 이 원소들의 답은 -1, 0, 또는 자기 자신이 될 수도 있다.
흔한 처리 방법 두 가지가 있다.
라이브 코딩에서는 1번이 코드 라인이 짧아 디버깅 표면적이 작다. 면접관이 코드를 따라 읽기에도 더 자연스럽다.
또 다른 트릭은 배열 끝에 가상의 "무한대" 원소를 추가했다고 가정하고, 마지막에 한 번 더 가상 원소로 비우는 패턴이다. 히스토그램 문제에서 자주 쓰이며, "원형 배열의 다음 큰 원소"처럼 wrap-around 가 있는 변형에서는 인덱스를 2*n 까지 돌리고 i % n으로 접근하는 변종이 등장한다.
Stack<Integer> 사용 — Java의 레거시 Stack 클래스는 Vector 상속이라 동기화 오버헤드가 있다. ArrayDeque를 쓰자. 면접관이 보고 "왜 ArrayDeque?"라고 물으면 점수 포인트가 된다.stack.peek()을 두 번 호출 — peek 후 pop 하기 전에 값을 변수에 담아두지 않으면 가독성이 떨어진다. 라이브 코딩에서는 int top = stack.peek() 한 줄로 의도를 드러내는 편이 좋다.!stack.isEmpty() && ... 를 빼먹어 NoSuchElementException. 화이트보드에서 short-circuit 평가 순서가 중요하다는 것을 알고 있어야 한다.stack.peek() < arr[i] 처럼 인덱스와 값을 비교하는 실수. 반드시 arr[stack.peek()] < arr[i].면접관이 보고 있는 화면에서 코드를 곧장 치기 전에, 30~60초 동안 다음 순서로 말로 풀이를 설명하라. 이 단계에서 면접관이 힌트를 주거나 잘못된 가정을 교정해 준다.
이 7단계는 외워서 토하는 게 아니라 사고 과정을 말로 옮기는 훈련이다. 시니어 라이브 코딩에서는 답을 빨리 적는 것보다 의사결정 흐름을 보여주는 것이 더 높이 평가된다.
라이브 코딩 대비는 IDE 자동완성에 의존하지 않는 환경에서 연습해야 한다. 다음 두 가지 중 하나를 추천한다.
Solution.java 한 파일에 public class Solution { public static void main ... } 구조를 두고, javac Solution.java && java Solution. JDK 17+ 권장.Main 클래스 안에 Scanner로 표준 입력을 읽고, 메서드 시그니처는 문제에서 주어진 그대로. Scanner 대신 BufferedReader를 쓰는 습관을 들이면 N=10⁶에서도 안전하다.자동완성 없는 상태로 30분 안에 두 문제를 푸는 훈련을 일주일에 두 번씩만 해도 라이브 코딩 직전에 손이 굳지 않는다.
정수 배열 temperatures가 주어진다. 각 인덱스 i에 대해, i 이후로 처음으로 temperatures[i]보다 더 따뜻한 날까지 며칠을 기다려야 하는지 를 담은 배열을 반환하라. 그런 날이 없으면 0을 채운다.
[73, 74, 75, 71, 69, 72, 76, 73][1, 1, 4, 2, 1, 1, 0, 0]1 ≤ N ≤ 10^5, 30 ≤ temperatures[i] ≤ 100먼저 스스로 종이에 단조 감소 스택을 그려보고, 인덱스 저장 패턴으로 손코딩한 뒤 아래를 펼친다.
스택에 인덱스를 넣고 단조 감소를 유지한다. 새 인덱스 i가 들어올 때, 스택 top의 온도가 temperatures[i]보다 엄격히 작으면 pop 하면서 그 인덱스의 답을 i - popped로 기록한다. 같은 온도에서는 pop 하지 않는다 ("더 따뜻한"이 strict이기 때문). 결과 배열은 0으로 초기화하므로 끝까지 남은 인덱스는 자동으로 0.
복잡도: 시간 O(N), 공간 O(N).
흔한 함정: <= 로 잘못 쓰면 같은 온도일 때도 pop 되어 오답. "strict 비교"를 처음 분석할 때 적어두면 막힌다.
import java.util.ArrayDeque;
import java.util.Deque;
public class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int n = temperatures.length;
int[] answer = new int[n]; // 0으로 초기화됨
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]) {
int popped = stack.pop();
answer[popped] = i - popped;
}
stack.push(i);
}
// 스택에 남은 인덱스는 더 따뜻한 날을 못 만난 경우 → answer가 이미 0
return answer;
}
public static void main(String[] args) {
int[] t = {73, 74, 75, 71, 69, 72, 76, 73};
int[] ans = new Solution().dailyTemperatures(t);
for (int v : ans) System.out.print(v + " ");
// 1 1 4 2 1 1 0 0
}
}면접에서 follow-up이 들어올 만한 지점:
음이 아닌 정수 배열 heights가 주어진다. 각 막대의 너비는 1이다. 이 히스토그램에서 만들 수 있는 가장 큰 직사각형의 넓이를 반환하라.
[2, 1, 5, 6, 2, 3]10 (인덱스 2~3, 높이 5, 너비 2 → 너비 2가 아니라 인덱스 2,3을 다 포함하는 5×2=10? 사실 정답은 인덱스 2~3 막대 두 개 모두 높이 ≥ 5 → 5×2=10.)1 ≤ N ≤ 10^5, 0 ≤ heights[i] ≤ 10^4이 문제는 monotonic stack의 "꽃" 이라 불릴 정도로 자주 나오고, 변형(0/1 매트릭스 최대 직사각형)도 많다. 라이브 코딩에서 이걸 30분 안에 푼다면 패턴 숙련도를 강하게 어필할 수 있다.
각 막대 i에 대해 "i를 높이로 사용할 때 만들 수 있는 최대 직사각형의 너비"를 구하면, 그 너비는 왼쪽으로 i보다 낮은 첫 막대의 인덱스 L과 오른쪽으로 i보다 낮은 첫 막대의 인덱스 R 사이 거리 R - L - 1로 결정된다. 면적은 heights[i] * (R - L - 1).
이걸 위해 보통 두 번 스캔(왼쪽 단조 증가 스택, 오른쪽 단조 증가 스택)으로 푸는 직관적 풀이가 있고, 한 번 스캔으로 끝내는 변형이 더 우아하다.
한 번 스캔 풀이는 다음 관찰에 기반한다.
t에 대해 면적을 계산한다.i - newTop - 1. 면적 = heights[t] * width.루프가 끝나면 스택에 남은 인덱스를 똑같은 방식으로 비운다 (오른쪽 경계는 n).
<=로 처리하는 이유: 같은 높이가 연속될 때 왼쪽 인덱스를 강제로 pop 시켜 새 인덱스가 그 영역을 다시 계산하도록 한다. 어차피 같은 높이라 면적은 동일하지만, pop 누락으로 인한 인덱스 꼬임을 막는다.
복잡도: 시간 O(N), 공간 O(N).
흔한 함정:
i - t 로 잘못 계산 (실제로는 i - newTop - 1).import java.util.ArrayDeque;
import java.util.Deque;
public class Solution {
public int largestRectangleArea(int[] heights) {
int n = heights.length;
Deque<Integer> stack = new ArrayDeque<>(); // 인덱스 저장, 단조 증가
int maxArea = 0;
for (int i = 0; i <= n; i++) {
int curHeight = (i == n) ? 0 : heights[i]; // 끝에 가상의 0 막대
while (!stack.isEmpty() && heights[stack.peek()] >= curHeight) {
int t = stack.pop();
int leftBoundary = stack.isEmpty() ? -1 : stack.peek();
int width = i - leftBoundary - 1;
int area = heights[t] * width;
if (area > maxArea) maxArea = area;
}
stack.push(i);
}
return maxArea;
}
public static void main(String[] args) {
int[] h = {2, 1, 5, 6, 2, 3};
System.out.println(new Solution().largestRectangleArea(h)); // 10
System.out.println(new Solution().largestRectangleArea(new int[]{2, 4})); // 4
System.out.println(new Solution().largestRectangleArea(new int[]{0, 0, 0})); // 0
}
}가상의 0 막대 트릭(i == n일 때 curHeight = 0)을 쓰면 루프가 끝난 뒤 스택을 따로 비우는 코드를 안 짜도 된다. 라이브 코딩에서 이 두 줄 차이가 시간 압박 상황에서 큰 차이를 만든다. 면접관이 "왜 i를 n까지 돌리는가?"라고 물으면 이 가상 막대로 잔여 처리 코드를 통합한 것이라고 설명한다.
면접에서 follow-up이 들어올 만한 지점:
라이브 코딩이 끝난 뒤(혹은 채용 매니저 라운드에서) "최근에 푼 알고리즘 문제 중 인상 깊은 것"을 묻는 경우, monotonic stack은 자료구조의 amortized 분석을 자연스럽게 풀어낼 수 있는 소재라 점수 포인트가 된다. 다음 구조로 답하면 단순히 "monotonic stack을 알아요" 보다 한 단계 위로 들린다.
"다음으로 큰 원소를 찾는 류의 문제는 brute force가 O(N²)인데, 핵심 관찰은 '아직 답을 못 찾은 인덱스들이 단조 감소하는 형태로 쌓인다'는 점입니다. 이 단조성을 스택으로 유지하면, 각 원소가 한 번 들어가고 한 번 나오므로 amortized O(N)이 됩니다. 인덱스 저장으로 통일해서 거리 계산 변형까지 같은 패턴으로 푸는 습관을 들였고, 등호 처리(strict 비교 vs not)를 문제 진술에서 먼저 확인하는 단계를 루틴에 넣었습니다."
이 한 단락이 "패턴을 외운 게 아니라 분석과 함께 내재화했다"는 인상을 준다.
또, 백엔드 시스템 맥락과 연결하면 더 좋다. 단조 스택의 발상은 실시간 윈도우 통계 (예: 최근 N개 요청 중 최대 응답 시간)에서 monotonic deque로 일반화되는데, 이걸 알고 있으면 알고리즘 문제에서 시스템 사고로 이어가는 follow-up에 강하다.
Stack 대신 ArrayDeque 를 쓴다.arr[stack.peek()]로 한다.<) 인지 non-strict (<=) 인지 문제 진술에서 확인했다.!stack.isEmpty() && ... 의 short-circuit 순서를 지켰다.