[JS 백준] 17298.오큰수

https://www.acmicpc.net/problem/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이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.

출력

총 N개의 수 NGE(1), NGE(2), ..., NGE(N)을 공백으로 구분해 출력한다

 

내 풀이기록이다..

 

DFS로 풀려는 안좋은 습관으로 인해 메모리,시간이 초과됐다..

 

아래는 풀이다.

const filePath = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';

const [n,input] = require("fs")
  .readFileSync(filePath)
  .toString()
  .trim().split('\n');

  const N = Number(n); // 5
  const number = input.split(" ").map(v=>+v); // 3 5 2 5 7
  let stack = [];
  let result = [];
  // console.log(number);

  for(let i =0; i < number.length; i++){
    while(stack.length && number[i] > number[stack[stack.length-1]]){
      result[stack.pop()] = number[i];
    }
    stack.push(i);
  }

  while(stack.length){
    result[stack.pop()] = -1;

  }

  console.log(result.join(" "))

 

오큰수는 가장 먼저 만나는 가장 큰수를 저장하는 것이다.

이때 작은수의 값은 필요가 없다.

하지만 모든 수의 인덱스는 필요하다!!

stack에 모든 수의 인덱스를 저장하고

while문을 통해 스택의 마지막에 저장된 인덱스의 숫자와 현재 접근한 숫자의 값을 계속 비교해서

result에 저장한다.