백준 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)이 주어진다.

입출력 예

풀이

let input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
let n = +input.shift();
let numbers = input[0].split(" ");
let answer = [];

while(numbers.length){
    let target = numbers.shift();
    let stack = [];
    for(let x of numbers){
        if(x > target){
            stack.push(x);
        }
    }
    if(stack.length){
        answer.push(stack[0]);
    } else {
        answer.push(-1);
    }
}
console.log(answer.join(" "));

• 메모리 초과가 나왔다. 이동시간에 고민해본 방법을 구현해본건데 굉장히 맥이 빠진다... 하하 vscode에서는 제대로 리턴값이 나오긴 했다.

let input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
let n = +input.shift();
let numbers = input[0].split(" ");
let stack = [];

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

while(stack.length){
    numbers[stack.pop()] = -1;
}
console.log(numbers.join(" "));

• stack에는 인덱스 값이 저장이 된다.
• stack에 값이 들어 있으면(적어도 첫번째 원소는 아니란 소리) stack에 들어 있는 인덱스를 가진 numbers값과 현재 인덱스의 number 값을 비교한다.
• 현재 인덱스의 numbers 값이 더욱 크다면 앞 인덱스의 numbers 값을 현재 인덱스의 numbers 값으로 바꿔준다.
• [3,5,2,7] 을 생각 했을 때 i=0 일땐 stack에 0을 넣고 끝나고 i=1 일때 stack에 들어있는 인덱스 numbers[0]과 현재 인덱스 numbers[1]의 값을 비교해주는 것.
• 현재 인덱스의 numbers 값이 더 작다면 바뀌는 작업은 일어나지 않고 stack.pop() 도 일어나지 않고 인덱스 값을 stack에 push한다.
• stack에 남아 있는 인덱스 값들은 오큰수가 없는 인덱스들이 됨.
• pop하면서 -1을 할당해주면 마무리된다.

• 해답이 잘 안나와 다른 이의 코드를 분석하는 식으로 공부했다. 꽤나 어렵다...