[백준 17298번 오큰수 - node.js] [알고리즘 기초 1/2 ]

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)을 공백으로 구분해 출력한다.

 

예제 입출력

 

입력	출력
4 3 5 2 7	5 7 7 -1
4 9 5 4 8	-1 8 8 -1

 

풀이[node.js]

 

 

728x90

들어온 값의 길이만큼 돌면서, splited의 값이 stack의 마지막 값(인덱스)의 input값과 비교하여 splited의 값이 더 작으면 stack에 해당 splited의 인덱스를 넣어주고, stack의 길이가 0일 때에도 값을 넣어줍니다.

만약, stack의 마지막 값의 input이 splited의 값보다 더 크다면, stack에서 마지막 인덱스를 꺼내주고 해당 splited의 인덱스 값을 들어온 splited의 값으로 바꿔줍니다.

 

cases만큼 다 돌고 나와서 stack에 값이 들어있다면, 해당 input에 대한 오큰수는 존재하지 않는 것이므로, -1을 입력해줍니다.

 

이 문제 방식은 stack에 input의 값을 넣어주고, 다음 인덱스의 input값이 stack에 들어있는 값보다 크다면 그 앞의 값들의 오큰수는 해당 input의 값이 되므로 input의 값을 아예 오큰수의 값으로 바꿔주는 방식입니다.

만약 stack에 값이 남아있다는 것은, 해당 인덱스 값이 가장 큰 수로 해당 값의 오른쪽에 더 큰 수가 없거나, 아예 비교할 다음 값이 없는 경우입니다.

 

var fs = require('fs');
var input = fs.readFileSync('/dev/stdin').toString().split('\n');
var cases = input[0];
var splited = input[1].split(' ');
var stack = [];
for(var i=0; i< Number(cases); i++){
    while(stack.length!==0 && Number(splited[i]) > Number(splited[stack[stack.length-1]])){
        splited[stack.pop()] = splited[i];
    }
    stack.push(i);
}

while(stack.length !== 0){
    splited[stack.pop()] = -1;
}
console.log(splited.join(' ').trim());