문제
크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.
예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.
입력
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.
출력
총 N개의 수 NGE(1), NGE(2), ..., NGE(N)을 공백으로 구분해 출력한다.
내풀이
const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
const input = fs.readFileSync(filePath).toString().split('\n')[1].split(" ").map(Number);
const result = new Array(input.length).fill(-1); // 결과 담을 배열 -1로 초기화
const stack = []; // 인덱스 저장할 배열
for (let i = 0; i < input.length; i++) {
// 스택에 값이 있고 스택의 맨 뒤의 값이 현재의 인풋값보다 작을 때
while (stack.length > 0 && input[stack.at(-1)] < input[i]) {
// stack 에서 인덱스값을 꺼내고
const index = stack.pop();
// 결과에 인덱스 위치를 넣고 현재 값 저장
result[index] = input[i];
}
// 인덱스 push
stack.push(i);
}
console.log(result.join(' '));