https://www.acmicpc.net/problem/6198
6198번: 옥상 정원 꾸미기
문제 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으
www.acmicpc.net
📌 작성한 코드
// 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 - 탑
https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사
youme016.tistory.com
백준에서 제공하고 있는 설명을 보면 각 건물에서 볼 수 있는 건물의 개수(현재 건물보다 오른쪽에서 낮은 건물 수)를 세는 방식으로 진행하고 있다. 하지만 그렇게 세는 것은 시간이 너무 많이 소요된다. 우리는 stack을 이용하여 현재 건물을 볼 수 있는 건물의 개수를 셀 것이다.
왼쪽 건물부터 stack에 추가하면서, 우리는 현재 건물 보다 높이가 낮은 건물이 나오면 stack에서 제거 할 것이다. 현재 건물 보다 낮은 건물은 현재 건물을 볼 수가 없으므로 개수를 셀 필요가 없고, 추후에 나올 건물들도 높이가 현재 건물 보다 높지 않으면 어차피 그 왼쪽의 건물은 보지 못하게 되기 때문에 사용될 일이 없어서 stack에서 완전히 제거해버릴 것이다. (이미지에서 4는 어차피 3을 볼 수 없다. 7에 가려져서 안보이기 때문이다. 해서 3는 앞으로도 카운트 될 일 없는 건물이기 때문에 제거한다.)

✅ 성공

'알고리즘 > 백준' 카테고리의 다른 글
| [JavaScript/Queue] 백준 실버 4 : 2164 - 카드 2 (0) | 2024.01.22 |
|---|---|
| [JavaScript/Stack] 백준 골드 4 : 17298 - 오큰수 (0) | 2024.01.22 |
| [JavaScript/Stack] 백준 골드 5 : 2493 - 탑 (2) | 2024.01.21 |
| [JavaScript/Stack] 백준 실버 2 : 1874 - 스택 수열 (0) | 2024.01.21 |
| [JavaScript] 백준 실버 4 : 10828 - 스택 (1) | 2024.01.21 |