스택과 단조 스택

템플릿 엔진이 {{#if}}와 {{/if}}의 짝을 확인한다. 설정 파일 검증기는 괄호와 대괄호가 제대로 닫혔는지 본다. 편집기는 Ctrl+Z를 누를 때마다 가장 최근 편집부터 되돌린다. 주가 차트에는 "이날 이후 처음으로 더 높았던 날"을 표시한다.

네 장면 모두 가장 최근에 넣은 것을 먼저 꺼내는 구조로 풀린다. 이 구조가 스택(stack)이다. 이 장은 스택으로 괄호 짝을 검사하고, 스택 안의 값을 한 방향으로 정렬된 상태로 유지하는 단조 스택(monotonic stack)으로 "다음 더 큰 값"을 한 번 훑기로 구한다. 개념 정리는 스택 노트에 있다.

스택: 마지막에 넣은 것을 먼저

스택은 한쪽 끝(맨 위)에서만 넣고 꺼낸다. 마지막에 넣은 것이 먼저 나오는 이 규칙을 LIFO(last-in, first-out)라고 한다. 따로 자료 구조를 만들 필요 없이 배열의 끝을 맨 위로 쓰면 된다.

1const stack: string[] = []2stack.push('a')3stack.push('b')4stack[stack.length - 1] // 'b'5stack.pop() // 'b'6stack.pop() // 'a'7stack.pop() // undefined

JavaScript pop()은 배열의 마지막 원소를 빼서 돌려주고, 빈 배열이면 undefined를 돌려준다(MDN: Array.prototype.pop). Python 튜토리얼도 리스트를 스택으로 쓸 때 append()로 넣고 인덱스 없는 pop()으로 꺼내라고 안내한다. 빈 리스트에서 pop()을 부르면 IndexError가 난다(Python 튜토리얼: 리스트를 스택으로 쓰기). 끝에서 넣고 빼는 것은 평균 O(1)이다(Python Wiki: TimeComplexity). 반대로 맨 앞에서 빼면 나머지 원소를 모두 한 칸씩 옮겨야 해서 느리다.

빈 스택에서 꺼낼 때 한 언어는 조용히 undefined를, 다른 언어는 예외를 낸다는 차이를 기억해 두자. 다음 절의 괄호 검사기에서 바로 쓰인다.

실행 취소(undo)도 스택이다. 편집할 때마다 이전 상태를 undo 스택에 넣고, Ctrl+Z를 누르면 맨 위를 꺼내 되돌린다. 되돌린 상태를 다시 살리는 다시 실행(redo)은 두 번째 스택에 쌓는다. 새로 편집하면 다시 실행할 것이 없어지므로 redo 스택을 비운다.

괄호 검사기: 닫을 때 맨 위를 확인한다

여는 괄호는 스택에 쌓는다. 닫는 괄호를 만나면 맨 위를 꺼내 짝인지 본다. 가장 최근에 연 괄호가 가장 먼저 닫혀야 한다는 규칙이 스택의 LIFO와 똑같다. 다 읽은 뒤 스택이 비어 있어야 모든 괄호가 닫힌 것이다.

1const text = 'f(a[0], {b})'2const pairs: Record<string, string> = { ')': '(', ']': '[', '}': '{' }3const stack: string[] = []4let result = ''5for (let i = 0; i < text.length; i++) {6  const ch = text[i]7  if ('([{'.includes(ch)) {8    stack.push(ch)9  } else if (')]}'.includes(ch)) {10    const top = stack.length > 0 ? stack.pop() : ''11    if (top !== pairs[ch]) {12      result = `${i}번 '${ch}'의 짝이 없다`13      break14    }15  }16}17if (result === '' && stack.length > 0) result = `닫히지 않은 괄호 ${stack.length}개`18if (result === '') result = '짝이 맞다'19console.log(result)

짝이 맞다

단조 스택: 다음 더 큰 값

날짜순 가격 prices가 있다. 날마다 그 뒤로 처음 나오는 더 높은 가격(없으면 -1)을 구한다. 날마다 오른쪽을 모두 훑으면 O(n²)이다.

한 번 훑기로 바꾸는 방법은 이렇다. 아직 답을 못 찾은 날의 위치를 스택에 쌓아 둔다. 새 가격이 스택 맨 위 날의 가격보다 큰 동안 맨 위를 계속 꺼내며 "네 답은 지금 가격이다"라고 적는다. 예를 들어 스택에 쌓인 날들의 가격이 [7, 5, 4](맨 위 날의 가격이 4)일 때 가격 6인 날이 오면 가격 4, 5인 날을 꺼내고 7인 날에서 멈춘다. 그런 다음 지금 날을 쌓는다. 꺼낸 위치는 다시 넣지 않는다. 이렇게 하면 스택 안의 가격은 바닥에서 맨 위로 갈수록 작아지거나 같은 순서(단조 비증가, monotonic non-increasing)를 늘 유지한다. 같은 가격은 꺼내지 않고 함께 쌓인다. 맨 위보다 큰 값이 오면 그 값보다 작은 것은 모두 꺼내지기 때문이다.

1const prices = [2, 7, 3, 5, 4, 6, 8]2const answer: number[] = new Array(prices.length).fill(-1)3const stack: number[] = []4for (let i = 0; i < prices.length; i++) {5  while (stack.length > 0 && prices[stack[stack.length - 1]] < prices[i]) {6    const j = stack.pop()!7    answer[j] = prices[i]8  }9  stack.push(i)10}11console.log(answer.join(', '))

7, 8, 5, 6, 6, 8, -1

while 안의 pop이 있는데 왜 O(n)일까

for 안에 while이 있으면 O(n²)처럼 보인다. 하지만 세는 단위를 바꾸면 다르다. 위치 하나는 스택에 한 번 들어가고, 많아야 한 번 나온다. 꺼낸 위치를 다시 넣는 코드는 없다. 그래서 전체 실행 동안 push는 정확히 n번, pop은 많아야 n번이다. while 조건 검사도 pop 한 번마다 한 번, 그리고 for 한 바퀴마다 멈추는 한 번이라 많아야 2n번이다. 모두 더해 O(n)이다.

for 한 바퀴가 아니라 전체 실행을 통틀어 세는 이 방식은 0장 보너스의 분할 상환 분석(amortized analysis, 여러 번의 연산에 비용을 나눠 보는 분석)과 같은 생각이다. 어떤 날은 while이 여러 번 돌지만, 그만큼 앞에서 쌓아 둔 위치가 줄어든 것이다.

단조 스택은 "다음 더 큰 값"만이 아니라 "이전 더 작은 값", "이 막대가 왼쪽·오른쪽으로 얼마나 펼쳐질 수 있나" 같은 질문에도 쓴다. 비교 방향(<인지 >인지)과 스택의 정렬 방향만 바꾸면 된다. 장 끝 보너스 문제가 그 예다.

실무 코드에서 찾아보기

정리하면 틀린 줄은 셋이다. 끝난 뒤 스택이 비었는지 확인하지 않아 '(('가 통과하고, 꺼내기를 while 대신 if로 써서 맨 위 하나만 답을 얻고, 스택에 위치 대신 값을 넣어 엉뚱한 칸에 답을 적는다.

heights = [3, 1, 4, 5, 1, 3] → 8 (높이 4, 폭 2: 2번·3번 막대)
heights = [3, 3, 3] → 9