[백준 / NodeJS] 17298번 오큰수

 

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

17298번: 오큰수

 

 

---

1. 문제 설명

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

 

 

 

---

2. 입출력

입출력

 

 

 

---

3. 문제 풀이

Stack에 인덱스를 저장하고 꺼내면서 각 숫자의 오큰수 비교 후 오큰수면 pop 아니면 다음 인덱스를 push 한다. 

const [n, arr] = require("fs")
  .readFileSync("./input.txt")
  .toString()
  .trim()
  .split(/\r\n/);

//const [n, ...arr] = require("fs").readFileSync("/dev/stdin").toString().trim().split(/\n/);
function solution(arr) {
  arr = arr.split(" ");
  const stack = []; // stack에는 오큰수를 구할 인덱스를 저장한다.
  for (let i = 0; i < arr.length; i++) {
  
    // 1) stack의 길이가 0이 아니면서, stack의 Top 값이 현재 값보다 작다면(오큰수)
    while (stack.length && Number(arr[stack[stack.length - 1]]) < Number(arr[i])) {
    
      // 2) stack의 Top 인덱스를 가져와 값을 찾아
      arr[stack.pop()] = arr[i];
    }
    // 3) stack에 인덱스를 저장하는 이유는 오큰수를 구하게 되면 값을 찾아갈 수 있기 때문이다.
    stack.push(i);
  }

  while (stack.length) {
    // 4) 아직 stack에 담겨있는 값이 있다면 오큰수를 찾을 수 없는 값들이다.
    arr[stack.pop()] = -1;
  }

  console.log(arr.join(" "));
}
solution(arr);