[백준] 오큰수 (JS)

문제

https://www.acmicpc.net/problem/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. 이중 반복문을 사용하면 시간 초과가 발생한다.

• 각 원소마다 오른쪽 값을 모두 탐색하면 O(N²) 이 되어 시간 초과 발생

2. 스택을 활용해 오른쪽 큰 수를 효율적으로 찾는다.

• 스택의 top과 현재 값을 비교하며 오큰수를 찾는다.
• 현재 값이 top보다 크다면, top의 오큰수는 현재 값이 된다.
• 현재 값이 top보다 작으면, stack에 현재 인덱스를 저장하고 다음 값과 비교한다.

3. 배열을 -1로 초기화하여 오큰수가 없는 경우 -1을 출력

• 기본값을 -1로 설정하여, 오큰수를 찾지 못한 경우 자동으로 -1이 출력된다.

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

const NGEArr = input[1].split(" ").map(Number);
const answer = new Array(NGEArr.length).fill(-1);
const stack = [];

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

console.log(answer.join(" "));

결론

이 문제는 골드 4 난이도의 스택 문제로, 오큰수를 찾는 문제이다.

스택을 활용하여 오른쪽 값과 스택에 저장된 왼쪽 인덱스를 비교함으로써, 오큰수 후보를 효율적으로 찾고 O(N)의 시간복잡도로 문제를 해결할 수 있었다.