[JavaScript] 백준 2493 탑 (JS)

탑

📚 문제 설명

랜덤한 크기의 건물들이 가로로 서 있고 해당 건물들은 서로 왼쪽으로 신호를 보내고 해당 신호는 더 높은 건물만 받을 수 있다.
아래 예시를 보면 좀 이해가 쉽다.

예시

건물 : 6, 9, 5, 7, 4
- 6은 자신보다 큰 건물이 없다  => 0
- 9는 자신보다 큰 건물이 없다  => 0
- 5는 왼쪽에 자신보다 큰 건물인 크기 9의 2번째 건물이 있다.  => 2
- 7의 왼쪽에 자신보다 큰 건물은 크기 9의 2번째 건물이다. =>2
- 4의 왼쪽에 자신보다 큰 건물은 크기 7인 4번쨰 건물이다. => 4

결과 : 0, 0, 2, 2, 4

👨🏻‍💻 풀이 과정

이 문제는 일전에 풀었던 옥상 정원 꾸미기 문제와 유사하다. 따라서 해당 문제와 똑같이 Monotonic Stack(단조스택)을 이용하여 풀면 될 것으로 보인다.
이 문제와 옥상 정원 꾸미기 문제의 다른점은 왼쪽에 있는 건물 중 자신의 크기보다 큰 건물 하나를 찾는다는 점
그리고 해당 건물이 몇번째 건물인지를 찾아야한다는 점이 다르다.
이 점을 주의해서 코드를 작성해보자.

• MonotonicStack 이 내림차순이 되도록 만든다.
• 만약 MonotonicStack 의 길이가 1이면 answer 배열에 0을 넣는다.
  • 아니라면 MonotonicStack 의 마지막에서 2번쨰 값의 인덱스 값을 indexOf() 를 이용해 찾아서 +1 한 후 answer에 추가

첫번째 풀이

    let fs = require("fs");
    let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
    let N = input.shift();
    input = input.shift().split(' ').map(Number);

    let MonotonicStack = [];
    let answer = [];

    for (let i = 0; i < input.length; i++) {
      	// 만일 스택에 값이 있다면
        if (MonotonicStack.length !== 0) {
          // 스택이 내림차순이 될 때까지 제거
            while (MonotonicStack.length) {
                if (MonotonicStack[MonotonicStack.length - 1] < input[i]) {
                    MonotonicStack.pop();
                }else {
                    break;
                }
            }
        }
      // 스택에 push
        MonotonicStack.push(input[i]);
      // 만일 스택의 길이가 1이면 0을 정답에 push
        if (MonotonicStack.length === 1) {
            answer.push(0);
        } else {
          // 스택의 마지막에서 2번째 건물의 인덱스 값을 찾아서 +1을 한 후 push
            answer.push(input.indexOf(MonotonicStack[MonotonicStack.length - 2]) + 1);
        }
    }
    console.log(answer.join(' '));

그런에 위에서 보이듯 해당 코드는 시간 초과가 나게 된다.
처음 코드를 작성하면서도 애매했지만, indexOf() 를 이용해 매번 찾는것 때문에 문제가 발생한 것으로 생각했다.
indexOf() 의 시간 복잡도는 검사 시작 지점에 따라 다르겠지만, 최악의 경우 O(n)이기 때문이다.

따라서 MonotonicStack 에 인덱스 값인 i 를 추가하는 방식으로 바꾸게 되었다.

수정한 코드

    let fs = require("fs");
    let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
    let N = input.shift();
    input = input.shift().split(' ').map(Number);

    let MonotonicStack = [];
    let answer = [];

    for (let i = 0; i < input.length; i++) {
        if (MonotonicStack.length !== 0) {
            while (MonotonicStack.length) {
              // 스택에는 인덱스 번호만 들어있기 때문에 input 배열에 넣어서 비교 
                if (input[MonotonicStack[MonotonicStack.length - 1]] <= input[i]) {
                    MonotonicStack.pop();
                }else {
                    break;
                }
            }
        }
      // 인덱스 값을 push
        MonotonicStack.push(i);
        if (MonotonicStack.length === 1) {
            answer.push(0);
        } else {
            answer.push(MonotonicStack[MonotonicStack.length - 2] + 1);
        }
    }
    console.log(answer.join(' '));

다행히 indexOf() 때문에 발생한 문제가 맞았다.

🧐 후기

전에 풀었던 Monotonic Stack(단조 스택)을 다시 한번 복습할 수 있었던 좋은 문제였다.
비록 스택에 인덱스 값을 넣지 않아서 시간 초과를 겪게 되었지만 생각한대로 문제가 해결되어서 다행이었다.