[JavaScript] 백준 골드 5 : 6198 - 옥상 정원 꾸미기

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

6198번: 옥상 정원 꾸미기

---

📌 작성한 코드

// 6198
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Gold/test.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

const N = parseInt(input.shift());
const buildings = input.map(Number);

const stack = [];
let answer = 0;

for (let i = 0; i < N; i++) {
    while (stack.length > 0 && stack[stack.length - 1] <= buildings[i]) {
        stack.pop();
    }
    // 현재 건물을 볼 수 있는 건물의 개수 더해주기
    answer += stack.length;

    stack.push(buildings[i]);
}

console.log(answer);

 

✅ 풀이 

2493 - 탑 문제와 유사하게 건물의 높이를 비교해서 풀어야 하는 문제이다. 탑에서 사용했던 방식으로 풀려다가 헤매서 시간이 조금 오래 걸렸던 문제이다.

https://youme016.tistory.com/322

[JavaScript/Stack] 백준 골드 5 : 2493 - 탑

 

백준에서 제공하고 있는 설명을 보면 각 건물에서 볼 수 있는 건물의 개수(현재 건물보다 오른쪽에서 낮은 건물 수)를 세는 방식으로 진행하고 있다. 하지만 그렇게 세는 것은 시간이 너무 많이 소요된다. 우리는 stack을 이용하여 현재 건물을 볼 수 있는 건물의 개수를 셀 것이다.

 

왼쪽 건물부터 stack에 추가하면서, 우리는 현재 건물 보다 높이가 낮은 건물이 나오면 stack에서 제거 할 것이다. 현재 건물 보다 낮은 건물은 현재 건물을 볼 수가 없으므로 개수를 셀 필요가 없고, 추후에 나올 건물들도 높이가 현재 건물 보다 높지 않으면 어차피 그 왼쪽의 건물은 보지 못하게 되기 때문에 사용될 일이 없어서 stack에서 완전히 제거해버릴 것이다. (이미지에서 4는 어차피 3을 볼 수 없다. 7에 가려져서 안보이기 때문이다. 해서 3는 앞으로도 카운트 될 일 없는 건물이기 때문에 제거한다.)

---

✅ 성공