[BEAKJOON / node.js] 17298 오큰수

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

//test.txt
4
3 5 2 7

---

sol1 - 시간 초과❌

let [N,...input] = require('fs').readFileSync('test.txt').toString().trim().split('\n');
let arr = input[0].split(' ').map(Number)
let answer = [];
for(let i=0;i<N-1;i++) {
  let max = Math.max(...arr);
  if(arr[0] === max) {
    answer.push(-1);
    arr.shift();
  }
  for(let j=i+1;j<N;j++) {
    if(arr[i]<arr[j]) {
      answer.push(arr[j]);
      break;
    }
  }
  
}
answer.push(-1)
console.log(answer.join(' '));
//5 7 7 -1

stack을 안 들고 풀어봤는데 테스트 케이스는 통과하지만 결과적으로 시간 초과가 난다. 단순히 배열을 한 칸씩 돌면서 다음 요소보다 작으면 다음 요소를 answer로 넘기는 식이었다. vscode 기준 이 방법이 sol2 보다 처리속도가 약 3배 가까이 느리다.

 

---

sol2

let [N,...input] = require('fs').readFileSync('test.txt').toString().trim().split('\n');

function solution(N,input) {
  let arr = input[0].split(' ').map(Number);
  let answer = Array.from({length:N},() => -1);
  let stack = [];
  for(let i=0;i<N;i++) {
    while(stack.length && arr[stack[stack.length-1]]<arr[i]) {
      answer[stack.pop()] = arr[i];
    }
    stack.push(i);
  }
  return answer.join(' ');
}
console.log(solution(N,input));
// 5 7 7 -1

stack을 이용해 풀었다. for 문을 돌면서 현재 요소가 앞전 요소보다 작다면 스택에 담으면서 계속 지나간다. while문에 걸리게 되면 쌓아둔 스택을 한 번에 처리할 수 있다.

// i = 0 for문에 들어오면 stack은 비어있기 때문에 while문을 지나치고 0을 스택에 넣는다.
answer = [-1, -1, -1, -1];
stack = [0];

// i = 1 while문에 걸리게 된다. (1. 스택에 요소가 있음 && 2. arr[0]<arr[1])
// answer[0] = arr[1]
answer = [5, -1, -1, -1];
stack = [1]; // while 문이 다 돌고나면 현재 index를 stack에 담아주고 다음 for문으로

// i = 2 while문에 걸리지 않기 때문에 stack에 index만 넣어주고 끝난다. (스텍에 요소는 있지만 arr[1] > arr[2])
answer = [5, -1, -1, -1];
stack =[1, 2];

// i = 3 while문에 걸리고, 조건이 맞지 않을 때까지 반복한다.
// 1.
//answer[2] = arr[3]
answer = [5, -1, 7, -1];
stack = [1];
//2.
//answer[1] = arr[3]
answer = [5, 7, 7, -1];
stack = [];

// 최종적으로 for문이 끝나게 되면
answer = [5, 7, 7, -1];
stack = [3];

비슷한 원리로 해결할 수 있는 프로그래머스 큰 수 만들기 도 같이 해결해보면 이해가 쉬울 것이다.