[백준] 옥상 정원 꾸미기 (JS)

문제

https://www.acmicpc.net/problem/6198

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

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

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

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

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

 

입력

첫 번째 줄에 빌딩의 개수 N이 입력된다.(1 ≤ N ≤ 80,000)

두 번째 줄 부터 N+1번째 줄까지 각 빌딩의 높이가 hi 입력된다. (1 ≤ hi ≤ 1,000,000,000)

출력

각 관리인들이 벤치마킹이 가능한 빌딩의 수의 합을 출력한다.

 

풀이

1. 스택을 활용한다.

2. 현재 빌딩과 다음 빌딩의 높이를 비교하여 현재 빌딩의 높이가 크면 answer에 stack의 크기만큼 더해준 후 push한다.

3. 현재 빌딩의 높이가 다음 빌딩의 높이보다 작거나 같으면 큰 빌딩이 나올 때까지 pop한다. 

4. 2, 3번을 n번 반복한 후 answer를 출력한다.

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

const [n, ...building] = input.map(Number);
const stack = [];
let answer = 0;

for (let i = 0; i < n; i++) {
    while (stack.length > 0 && stack[stack.length - 1] <= building[i]) {
        stack.pop();
    }
    
    answer += stack.length;
    stack.push(building[i]);
}

console.log(answer);

결론

골드5 문제이다.

이중 포문으로 풀면 런타임 초과가 발생한다. 스택을 활용하여 조건에 맞게 push or pop하면 O(n)으로 해결할 수 있다.