https://www.acmicpc.net/problem/17298
17298번: 오큰수
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.
www.acmicpc.net
📌 작성한 코드
// 17298
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 = Number(input[0]);
const numbers = input[1].split(" ").map(Number);
const stack = [];
const answer = [];
for (let i = N - 1; i >= 0; i--) {
while (stack.length && stack[stack.length - 1] <= numbers[i]) {
stack.pop();
}
stack.length === 0 ? answer.push(-1) : answer.push(stack[stack.length - 1]);
stack.push(numbers[i]);
}
console.log(answer.reverse().join(" "));
📌 풀이
stack을 사용해서 오른쪽에 위치한 값 중 가장 가까우면서 현재 값보다 큰 값을 찾는 문제이다.
오른쪽 기준으로 더 큰 값을 찾고싶으므로, 순회를 뒤에서부터 돌아주면서 해당 값보다 큰 값이 나올 때 까지 stack.pop()해서 삭제해주면 된다.
이전에 푼 탑 문제의 해설을 보면 왜 이렇게 풀어야 하는지 잘 이해할 수 있을 것이다.
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
✅ 성공

'알고리즘 > 백준' 카테고리의 다른 글
| [JavaScript/Deque] 백준 실버 4 : 10866 - 덱 (0) | 2024.01.23 |
|---|---|
| [JavaScript/Queue] 백준 실버 4 : 2164 - 카드 2 (0) | 2024.01.22 |
| [JavaScript] 백준 골드 5 : 6198 - 옥상 정원 꾸미기 (0) | 2024.01.22 |
| [JavaScript/Stack] 백준 골드 5 : 2493 - 탑 (2) | 2024.01.21 |
| [JavaScript/Stack] 백준 실버 2 : 1874 - 스택 수열 (0) | 2024.01.21 |