https://www.acmicpc.net/problem/2493
2493번: 탑
첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1
www.acmicpc.net
📌 작성한 코드
// 2493
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 towers = input.shift().split(" ").map(Number);
const stack = [];
const answer = [];
for (let i = 0; i < N; i++) {
const item = {
index: i + 1,
value: towers[i],
};
if (i === 0) {
stack.push(item);
answer.push(0);
continue;
}
while (stack.length > 0 && stack[stack.length - 1].value < towers[i]) {
stack.pop();
}
if (stack.length === 0) {
answer.push(0);
} else {
answer.push(stack[stack.length - 1].index);
}
stack.push(item);
}
console.log(answer.join(" "));
📌 풀이
현재 탑보다 큰 탑 중에 가장 가까운 탑에 레이저가 부딪히게 될 것이다. 그래서 우리가 찾아야 하는 탑은 왼쪽에서 가장 가깝고, 큰 탑이다.
우리는 stack을 사용해서 탑을 저장할 것인데, 매 번 현재 탑보다 큰 탑이 스택 안에 있는지 확인 할 것이다.
stack에 find를 사용해서 현재 탑보다 큰 탑이 있는지 확인하는 것은 시간이 많이 걸리고 복잡한 일이다.
그래서 우리가 사용할 방법은 현재 탑보다 작은 탑들은 stack에서 제거해버리는 것이다.
1. 현재 탑보다 작은 탑들은 어차피 현재 탑이 더 크기 때문에 추후에 나올 탑의 레이저는 현재 탑에 먼저 부딪히게 되어있다. 그래서 그 앞선 탑에 부딪힐 레이저가 없기 때문에 저장될 필요가 없다. 그래서 pop() 해서 stack에서 제거해 버릴 것이다.
2. 그렇게 pop 하다가 현재 탑보다 큰 탑을 발견하게 되면 해당 탑에 레이저가 부딪히게 되기 때문에 해당 탑의 인덱스를 답에 저장해준다.
3. 그리고 현재 탑이 추후에 나올 레이저에 맞는 탑이 될 수 있으므로 stack에 저장해준다.
아주 간단하게 설명하면
- 원하는 탑(현재 탑보다 큰 탑)이 나올 때까지 stack.pop()한다.
- 원하는 탑이 나오면 답으로 저장한다.
- 현재 탑을 stack에 저장한다.
이렇게 하면 계속해서 탐색하지 않고 간편하게 원하는 답을 구할 수 있다.

✅ 성공

'알고리즘 > 백준' 카테고리의 다른 글
| [JavaScript/Stack] 백준 골드 4 : 17298 - 오큰수 (0) | 2024.01.22 |
|---|---|
| [JavaScript] 백준 골드 5 : 6198 - 옥상 정원 꾸미기 (0) | 2024.01.22 |
| [JavaScript/Stack] 백준 실버 2 : 1874 - 스택 수열 (0) | 2024.01.21 |
| [JavaScript] 백준 실버 4 : 10828 - 스택 (1) | 2024.01.21 |
| [JavaScript/Queue] 백준 실버 4 : 1158 - 요세푸스 문제 (0) | 2024.01.21 |