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

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

2493번: 탑

---

📌 작성한 코드 

// 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에 저장한다. 

 

이렇게 하면 계속해서 탐색하지 않고 간편하게 원하는 답을 구할 수 있다.

 

✅ 성공