[백준] JS 17298번 오큰수

문제

백준 17298번 오큰수

크기가 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이다.

첫 풀이에서 개별적인 array에 오큰수에 해당하는 원소를 찾기 위해 매 원소마다 input으로 주어진 array만큼 탐색하니 결과는 시간초과.

이에 오큰수에 해당하는 인덱스를 스택에 push & pop하는 방향으로 풀었더니 시간초과를 해결하였다.

코드

const input = require("fs")
  .readFileSync(__dirname + "/input.txt")
  .toString()
  .trim()
  .split("\n")
  .map((x) => x.split(" ").map(Number));
let stack = [];
for (let i = 0; i < input[1].length; i++) {
  while (stack.length && input[1][stack[stack.length - 1]] < input[1][i]) {
    input[1][stack.pop()] = input[1][i];
  }
  stack.push(i);
}

while (stack.length > 0) {
  input[1][stack.pop()] = -1;
}

console.log(input[1].join(" "));

1. for문을 이용하여 스택에 오큰수에 해당하지 않는 인덱스를 추가한다.
2. 스택에 원소가 존재하고, 스택 맨 위의 원소가 현재 i가 가리키는 원소보다 크다면, pop하여 그것을 input[1][pop한 인덱스] 자리에 할당한다.
3. 반복.
4. 이제 stack에는 자신의 오른쪽에 자기보다 큰 수가 없는 수의 인덱스만 남는다. 남은 인덱스에 해당하는 input[1]의 원소들을 -1로 바꾸어 출력하면 된다.