Monotonic Stack에 대하여

• 알고리즘 문제를 풀다가 처음 마주하는 개념을 알게 되었다.
• 이름을 알게 된 김에 가볍게 내용을 정리해보았다.

---

Monotonic Stack이란

: 스택 내의 요소들이 단조적으로(Monotonic) 증가/감소하는 스택을 말한다. 아래와 같은 특징을 갖는다고 한다.

 

• 한 번 pop된 요소는 다시는 재사용 되지 않는다.
• 요소를 스택에 추가할 때마나 단조성을 유지한다.
  → 이러한 특징 때문에 주로 다음/이전의 최소값/최대값(Next/Previous smaller/larger Problem)을 구하는 문제에서 잘 쓰인다.

 

Monotonic Stack의 구현

 Monotonic Stack의 구현에는 아래의 과정을 거친다. 아래는 감소하는(Decreasing) 스택을 구하는 과정이다.

1. 기본적으로, 주어진 숫자 목록을 순회하며 요소를 스택에 집어 넣는다.
2. 이 때, 현재 넣으려는 요소가 스택의 top에 위치한 요소보다 클 경우, 해당 요소보다 작은 요소들을 스택에서 전부 pop한다.
   (반대로 증가하는 스택을 구현할 경우, 현재 요소가 top의 요소보다 작을 경우 pop을 수행하면 된다.)
3. pop이 끝나면, 그 때 현재 요소를 스택에 집어 넣는다.

⇒ 이 과정을 통해, 스택에 존재하는 요소들이 항상 내림차순(혹은 오름차순)인 상태가 보장된다.

 

장점

1. Motonic Stack을 사용함으로써 시간복잡도를 줄일 수 있다.
2. 범위 내 요소들의 최대/최소값을 관리할 수 있게 한다.

 

단점

1. 시간복잡도와는 반대로, 공간복잡도는 O(n)이 된다.
2. 한 번 pop한 요소는 다시 돌려놓을 수 없기 때문에, 다룰 때 주의해야 한다.

 

 

문제 풀이 - 백준 6198번 옥상 정원 꾸미기

  사실상 내가 이 스택에 대해 새롭게 알게 해준 원흉. 각 빌딩에서 관찰할 수 있는(자신보다 나중에 위치 + 자신보다 낮은 빌딩) 빌딩의 개수를 찾는 문제이다.

 

  생각할 수 있는 가장 간단한 풀이방법은, 각 빌딩을 순회하며 자신 다음에 위치하는 빌딩 중 자신보다 낮은 빌딩의 개수를 세서 하나하나 더하는 것이다. 다만 이 방법은 뭔가 아닌 것 같아서(...) 계속 다른 방법을 궁리하다가, 아무 생각이 안난 나머지 시험으로 제출했었다. 그런데 의외로 정답처리 되었다(?)...

 

  아래의 코드가 위의 방법을 그대로 구현한 것이다.

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input = [];

rl.on("line", (line) => {
  input.push(parseInt(line));
}).on("close", function () {
  const n = input.shift();
  let answer = 0;

  // 2중 for문을 사용하여 각 빌딩의 오른쪽에 위치하며 더 낮은 빌딩의 개수를 센다
  for (let i = 0; i < n; i++) {
   const current = input[i];
   let num = 0;

    for (let j = i + 1; j < n; j++) {
      if (input[j] < current) num++;
      else break;
    }
    answer += num;
  }

  console.log(answer);
  process.exit();
});

 

 

  다만 아무리 생각해도 이게 아니다 싶어서 찾아본 결과, Monotonic Stack이 나왔다. Monotonic Stack을 사용한 방법은 아래와 같은 과정을 거친다.

1. 빌딩 높이 배열을 순회하며 스택에 집어 넣는다.
2. 이 때, 위의 Monotonic Stack의 구현 방식처럼 현재 요소가 스택의 맨 위에 위치한 요소보다 클 경우, 자신보다 더 작은 요소가 없어질 때까지 스택에서 요소들을 빼낸다.
3. 요소들을 전부 빼내면, (남은 스택의 길이 - 1)을 합계에 더한다.

  3번의 해결책이 약간 이해가 안 갔는데, 실제 예제를 위 로직에 따라 테스트해보니 의미를 알 수 있었다.

 

예제를 위 로직에 따라 실행한 모습

 

  실행한 결과, (각 요소를 스택에 넣고 난 후의 스택의 길이 - 1) 가 해당 요소를 바라볼 수 있는 빌딩의 개수임을 알 수 있다. 이를 그대로 코드로 구현할 시 아래와 같다.

 

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input = [];

rl.on("line", (line) => {
  input.push(parseInt(line));
}).on("close", function () {
  const n = input.shift();
  let answer = 0;

  let stack = [input[0]];
  for (let i = 1; i < n; i++) {
    const current = input[i];
    while (stack.length && stack[stack.length - 1] <= current) {
      stack.pop();
    }

    stack.push(current);
    answer += (stack.length - 1);
  }

  console.log(answer);
  process.exit();
});

 

  위 방법으로 구현할 시, 전자의 방법에 비해 시간이 압도적으로 줄어든 반면, 메모리 사용량이 다소 증가한 것을 확인할 수 있었다. 

 

---

• 아직은 낯선 개념이라, 관련 예제를 좀더 많이 풀어봐야할 것 같다.
• 참고

https://www.geeksforgeeks.org/introduction-to-monotonic-stack-data-structure-and-algorithm-tutorials/

Introduction to Monotonic Stack - Data Structure and Algorithm Tutorials - GeeksforGeeks