[BOJ / Node.js] 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)을 공백으로 구분해 출력한다.

예제 입력 1 복사

4
3 5 2 7

예제 출력 1 복사

5 7 7 -1

 

Solve

• 다음과 같이 의사코드를 작성하며 풀이했습니다.

1. 전체 배열을 순회하는 루프 (n-1 까지)
2. 오큰수를 바로 찾을 수 있는지 검사(바로 오른쪽에 있는 경우)
3. 찾을 수 있다면 NGE 배열 index에 오큰수 저장.
4. 스택이 비어있지 않다면 스택의 맨 위 값이 오큰수가 가능한지 검사하고 가능하지 않을 때 까지 진행.
5. 찾을 수 없다면 스택에 넣기 (값, 인덱스 형태로)

• NGE 배열 생성 후 -1로 초기화 해주었습니다. (오큰수가 없는 경우 -1로 출력되는 것이 default값 이기 때문에 초기화를 해놓는다면 따로 처리하지 않아도 됨)

Code

const input = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n");

const n = +input[0];
const arr = input[1].split(' ').map(el=>+el);

const NGE = Array(n).fill(-1);
const stack = [];

for(let i = 0; i < n-1; i++) {
    if(arr[i] < arr[i+1]) {
        NGE[i] = arr[i+1]

        while(stack.length) {
        const [value, index] = stack[stack.length-1];
        if(arr[i+1] > value) {
            NGE[index] = arr[i+1];
            stack.pop();
        } else break;
    }
    
    }
    else stack.push([arr[i], i]);
}


console.log(NGE.join(' '));