단조 스택 — 알고리즘 · 오승의 기술블로그

원소마다 오른쪽에서 처음 나오는 더 큰 값을 찾을 때 씁니다. 아직 답을 못 찾은 원소를 스택에 쌓아 두었다가, 더 큰 값이 오면 맨 위부터 꺼내며 답을 정합니다. 모든 쌍을 비교하는 O(n²) 풀이가 O(n)으로 줄어듭니다.

언제 쓰나

배열의 원소마다 오른쪽에서 처음으로 나오는 더 큰 값(또는 더 작은 값)을 찾아야 할 때 씁니다.

“며칠을 기다려야 더 따뜻해지는가”, “몇 초 뒤에 가격이 처음 떨어지는가”처럼 원소마다 조건을 처음 만족하는 위치나 그 위치까지의 거리를 묻습니다.
답이 하나가 아니라 원소마다 하나씩, 입력과 같은 길이의 배열로 나옵니다.
입력이 10만 개 수준이라, 원소마다 오른쪽을 끝까지 훑는 O(n²) 풀이로는 제한 시간 안에 끝나지 않습니다.

어떻게 동작하나

날마다 오른쪽을 훑으면 같은 날을 여러 번 본다

LeetCode 739는 하루 기온이 담긴 배열 temperatures를 받아, 날마다 며칠을 기다려야 그날보다 따뜻한 날이 오는지 구하는 문제입니다. 끝까지 더 따뜻한 날이 없으면 0입니다. temperatures = [73, 74, 75, 71, 69, 72, 76, 73]이면 답은 [1, 1, 4, 2, 1, 1, 0, 0]입니다.

가장 먼저 떠오르는 방법은 날마다 다음 날부터 한 칸씩 오른쪽으로 가며 더 따뜻한 날을 찾는 것입니다.

2번 날 75도에서 출발하면 71, 69, 72를 지나 76에서 멈춥니다. 네 칸을 봤으니 답은 4입니다.
3번 날 71도에서 출발하면 69를 지나 72에서 멈춥니다.
4번 날 69도에서 출발하면 바로 다음 날 72에서 멈춥니다.

69와 72는 1번 과정에서 이미 지나간 날인데, 출발하는 날이 바뀔 때마다 다시 비교합니다. 기온이 계속 내려가기만 하는 입력이면 어느 날에서 출발해도 끝까지 가야 하므로 비교 횟수가 (n - 1) + (n - 2) + … + 1 = n(n - 1)/2입니다. n이 10만이면 약 50억 번입니다.

기다리는 날을 쌓아 두고, 따뜻한 날이 오면 한꺼번에 정한다

방향을 바꿔 보겠습니다. 날마다 앞을 내다보는 대신, 아직 더 따뜻한 날을 만나지 못한 날을 모아 두고 새 날이 올 때마다 그 날이 누구의 답이 되는지 확인합니다. 4번 날까지 처리하고 5번 날 72도를 보려는 순간을 그려 보면 다음과 같습니다.

오른쪽 스택에 2번 날 75도, 3번 날 71도, 4번 날 69도가 더 따뜻한 날을 기다리고 있고, 노란 칸의 72도를 막 보려는 참입니다. 0번 날과 1번 날은 바로 다음 날 답이 정해졌습니다.

72도는 69도보다 따뜻하니 4번 날의 답이 5 - 4 = 1로 정해지고, 71도보다도 따뜻하니 3번 날의 답이 5 - 3 = 2로 정해집니다. 75도는 72도보다 따뜻해서 계속 기다립니다. 이 장면에서 두 가지를 알 수 있습니다.

기다리는 날은 위로 갈수록 춥습니다. 새 날을 올리기 전에 그보다 추운 날을 모두 꺼내기 때문에, 어떤 날 아래에는 그날보다 따뜻하거나 같은 날만 남습니다.
그래서 맨 위부터 비교하면 됩니다. 맨 위의 날이 오늘보다 따뜻하면 그 아래 날들은 더 따뜻하니 볼 필요가 없습니다. 오늘보다 추운 날은 늘 위쪽에 몰려 있어서, 가장 나중에 올린 날부터 꺼내게 됩니다.

가장 나중에 넣은 것을 가장 먼저 꺼내는 자료구조가 스택(stack)입니다. 여기에 더해 스택 안의 값이 한 방향으로 정렬된 상태를 지키도록 넣고 빼는 방법을 단조 스택(monotonic stack)이라고 부릅니다. 단조(monotonic)는 값이 한 방향으로만 바뀐다는 뜻이고, 이 문제의 스택은 바닥에서 위로 갈수록 온도가 낮아지거나 같습니다.

코드에서는 세 가지 값을 기억합니다.

i: 오늘의 날짜 번호입니다. 0번 날부터 하루씩 갑니다.
stack: 아직 더 따뜻한 날을 만나지 못한 날의 번호입니다. 온도 대신 번호를 넣어야 꺼낼 때 i - 번호로 기다린 날 수를 셀 수 있고, 온도는 temperatures[번호]로 다시 읽습니다.
answer: 날마다 기다린 날 수입니다. 모두 0으로 채워 두고 시작하므로, 끝까지 스택에서 나오지 못한 날은 따로 처리하지 않아도 0이 남습니다.

오늘 i를 볼 때 할 일은 두 가지입니다.

맨 위의 날이 오늘보다 추우면 그날을 꺼내고 answer[그날] = i - 그날을 적습니다. 맨 위가 오늘보다 따뜻하거나 같아질 때까지, 또는 스택이 빌 때까지 반복합니다.
오늘을 스택에 올립니다. 오늘도 아직 더 따뜻한 날을 모르니 기다리는 쪽에 들어갑니다.

직접 따라가 보기

아래에서 “다음”을 누르면 오늘 칸이 노랗게 하루씩 옮겨 가고, 기다리는 날은 오른쪽 스택에 쌓이며, 답이 정해진 날에는 칸 줄 위로 호가 그어집니다. 8번째 단계에서 스택에 75, 71, 69도가 쌓이고, 9~10번째 단계에서 72도가 69도와 71도를 차례로 꺼냅니다. 13번째 단계에서는 2번 날 75도가 네 날을 기다린 끝에 76도를 만나 answer[2]가 4가 됩니다. 단계마다 스택이 아래에서 위로 갈수록 추운지도 함께 보세요.

칸 줄 아래의 작은 칸은 답이 정해진 날만 채웁니다. 변수 칸의 answer는 코드처럼 0으로 시작하므로, 아직 답을 모르는 날도 0으로 보입니다.

단계 1 / 16

변수

i: 0temperatures[0] = 73
stack: []
answer: [, 0, 0, 0, 0, 0, 0, 0, 0]

i = 0, 0번 날 73도부터 하루씩 봅니다. 스택은 비어 있고 answer는 모두 0으로 시작합니다. "다음"을 눌러 보세요

오늘 (i)
더 따뜻한 날을 기다리는 날 (stack)
정해진 답
답이 정해진 날
아직 안 본 날

LeetCode 739 예제 1. 아래 작은 칸 줄이 answer입니다. 빌드할 때 풀이를 실제로 돌려 기록한 단계입니다.

대표 문제 풀이

아래는 참고 풀이입니다. 주석의 ①②가 위의 두 규칙과 같은 순서이고, 변수 이름은 시각화의 변수 칸과 같습니다.

function dailyTemperatures(temperatures) {
  // answer[날짜 번호] = 더 따뜻한 날까지 기다린 날 수. 끝까지 못 찾은 날은 0 그대로 둔다
  const answer = new Array(temperatures.length).fill(0);
  // 아직 더 따뜻한 날을 만나지 못한 날의 번호. 바닥에서 위로 갈수록 온도가 낮다
  const stack = [];

  for (let i = 0; i < temperatures.length; i++) {
    // ① 맨 위의 날이 오늘보다 추우면 꺼내며 그날의 답을 적는다
    while (stack.length > 0 && temperatures[stack[stack.length - 1]] < temperatures[i]) {
      const waitingDay = stack.pop();
      answer[waitingDay] = i - waitingDay;
    }
    // ② 오늘도 더 따뜻한 날을 기다린다
    stack.push(i);
  }

  return answer;
}

①의 비교가 <=가 아니라 <인 이유는 같은 온도를 더 따뜻한 날로 치지 않기 때문입니다. 73도 다음 날이 73도라면 앞의 73도는 꺼내지 않고 계속 기다립니다.

for 안에 while이 있어 두 겹 반복처럼 보이지만, 시간은 O(n)입니다. 모든 날은 ②에서 스택에 한 번 올라가고 ①에서 많아야 한 번 꺼지므로, 전체 실행을 통틀어 while이 도는 횟수는 n을 넘지 않습니다. 공간은 스택에 쌓인 날 수만큼이고, 기온이 계속 내려가는 입력에서는 모든 날이 쌓여 O(n)입니다.

자주 하는 실수

날마다 훑는 풀이의 시간 복잡도를 n!로 잡습니다. 저는 처음에 이중 반복 풀이를 보고 “n개면 n!”이라고 답했습니다. 반복이 겹친 모양만 보고 짐작한 값이었습니다. 기온이 계속 내려가는 길이 4의 입력에서 날마다 비교하는 횟수를 직접 세어 보니 3, 2, 1, 0이었고 합은 6이었습니다. 이를 n으로 넓히면 n(n - 1)/2이므로 O(n²)입니다. 복잡도가 헷갈릴 때는 작은 최악 입력을 하나 정해 실제 연산 횟수를 세고 더해 보면 짐작보다 정확합니다.

스택이 가장 높이 쌓이는 입력을 반대로 짚습니다. 저는 공간 복잡도가 O(n)이라는 것은 맞혔지만, 최악 입력으로 [1, 2, 3, 4]처럼 기온이 오르는 경우를 들었습니다. 오르는 입력에서는 새 날이 올 때마다 바로 앞의 날을 꺼내므로 스택에 늘 한 날만 남습니다. 스택이 끝까지 쌓이는 것은 아래처럼 기온이 내려가기만 해서 아무 날도 꺼내지 못하는 경우입니다.

기온이 내려가기만 하면 모든 날이 스택에 남고, 반복이 끝난 뒤 answer는 모두 0입니다.

첫날을 반복문 밖에서 따로 넣습니다. 저는 0번 날을 스택에 미리 넣고 반복문을 i = 1부터 시작했는데, 종료 조건은 i <= temperatures.length로 적었습니다. 그러자 마지막 반복에서 범위 밖의 temperatures[8]을 읽어 undefined인 날을 스택에 올렸습니다. undefined와의 비교가 늘 false라서 답은 맞게 나왔지만, 없는 날이 스택에 남은 채로 끝났습니다. 위 풀이처럼 빈 스택으로 i = 0부터 시작하면 첫날도 다른 날과 같은 ①②를 거치고, 반복 범위도 i < temperatures.length 하나로 정해집니다.