Written by java-style
on 2021-10-21

오큰수 (17298번) [node.js, JavaScript]

문제 설명

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

의사코드

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

stack 배열에는 순차적으로 들어오는 input값들의 인덱스가 저장되게됩니다. 현재 값 arr[i]이 이전 arr[i-1] 값보다 크면 arr[i]이 바로 오큰수가 됩니다. 첫번째 반복문이 끝나면 오큰수를 찾지 못한 값들의 인덱스가 stack에 남아있게 됩니다. arr배열의 해당 인덱스에 -1을 할당합니다.

Code

const input = require("fs").readFileSync("/dev/stdin").toString().split("

"); solution(input); function solution(input) { const len = input[0]*1; const arr = input[1].split(" ").map(Number); const stack = []; for (let i = 0; i < len; i++){ while (stack.length !== 0 && arr[i] > arr[stack[stack.length - 1]]) { arr[stack.pop()] = arr[i]; } stack.push(i); } while(stack.length !== 0){ arr[stack.pop()] = -1; } console.log(arr.join(" ")); }

from http://jinblog123.tistory.com/157 by ccl(A) rewrite - 2021-10-21 16:27:48

Top