6198 옥상 정원 꾸미기 (node.js)

문제 

도시에는 N개의 빌딩이 있다.

빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다.

i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으로만 볼 수 있다.

i번째 빌딩 관리인이 볼 수 있는 다른 빌딩의 옥상 정원은 i+1, i+2, .... , N이다.

그런데 자신이 위치한 빌딩보다 높거나 같은 빌딩이 있으면 그 다음에 있는 모든 빌딩의 옥상은 보지 못한다.

예) N=6, H = {10, 3, 7, 4, 12, 2}인 경우

             = 
 =           = 
 =     -     = 
 =     =     =        -> 관리인이 보는 방향
 =  -  =  =  =   
 =  =  =  =  =  = 
10  3  7  4  12 2     -> 빌딩의 높이
[1][2][3][4][5][6]    -> 빌딩의 번호

• 1번 관리인은 2, 3, 4번 빌딩의 옥상을 확인할 수 있다.
• 2번 관리인은 다른 빌딩의 옥상을 확인할 수 없다.
• 3번 관리인은 4번 빌딩의 옥상을 확인할 수 있다.
• 4번 관리인은 다른 빌딩의 옥상을 확인할 수 없다.
• 5번 관리인은 6번 빌딩의 옥상을 확인할 수 있다.
• 6번 관리인은 마지막이므로 다른 빌딩의 옥상을 확인할 수 없다.

따라서, 관리인들이 옥상정원을 확인할 수 있는 총 수는 3 + 0 + 1 + 0 + 1 + 0 = 5이다.

====

문제 풀이

기준이 되는 빌딩은 오른쪽에 있는 건물들만 볼 수 있다.

만약 input의 값이 작았다면 N^2의 시간 복잡도를 통해 끝 -1 노드부터 탐색하면서 자기보다 작은 빌딩의 갯수를 count 해주면 된다.

하지만 input의 값은 8만개까지 들어올 수 있으므로 N의 시간 복잡도로 해결해주는 것이 베스트이다.

그러기 위해선 탐색을 하면서 지금까지의 건물들을 기억해줄 기록 배열이 필요하다.

이를 stack으로 선언한다.

stack에는 건물의 높이와 그 건물에서 관측했던 건물의 갯수를 기록해줄 것이다.

현재 빌딩의 높이를 기준으로 stack의 끝에서부터의 높이가 클때까지 계속 pop해준다. pop이 되는 값은 이 건물의 높이보다 작은 것이 된다. pop한 요소에는 그 높이에서 관측할 수 있는 갯수가 기록되어 있으므로 현재 빌딩에서도 관측이 되는 요소들인 것이다. 또한 pop된 요소 또한 현재 빌딩보다 작은 빌딩인 것이므로 이를 감안하여 관측할 수 있는 갯수에 +1 을 해준다.

만약 높이가 10,5,7,4,3,2,1,6,2 이라면 끝에서부터

[2,0]

[6,1]       => 1

[6,1] [1,0]  

[6,1] [2,1]   =>1

[6,1] [3,2]    =>2

[6,1] [4,3]     =>3

[7,6]            =>6

[7,6] [5,0]

[10,8]        =>8

const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');

const n = +input[0];
const arr = input.slice(1).map(Number);

let answer = 0;
const stack = [[arr[n - 1], 0]];

for (let i = n - 2; i > -1; i--) {
    const value = arr[i];
    let cnt = 0;

    while (stack.length && stack[stack.length - 1][0] < value) {
        const [_, c] = stack.pop();
        cnt += c;
        cnt++;
    }
    answer += cnt;
    stack.push([value, cnt]);
}

console.log(answer);