[boj] 17298. 오큰수

[boj] 17298. 오큰수

• 문제 링크 : https://www.acmicpc.net/problem/17298
• 사용 언어 : Node.js

17298번: 오큰수

크기가 N인 수열 $ A = A_1, A_2, ..., A_N $이 있다. 수열의 각 원소 $ A_i $ 에 대해서 오큰수 $ NGE(i) $ 를 구하려고 한다. $ A_i $ 의 오큰수는 오른쪽에 있으면서 $ A_i $ 보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -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 $이다.

---

 

1. 문제 분석

각 수를 기준으로 해당 수보다 오른쪽에 있는 수들 중 큰 수들 중에서 가장 왼쪽에 있는 수를 찾는 문제입니다.
먼저 원시적으로 각 원소마다 오른쪽에 있는 수를 비교 검사하는 방법이 있습니다.
이 경우 시간복잡도는 $ O(N^2) $ 이 나오게 되고 입력값의 범위가 $ 1,000,000 $이기에 시간 초과가 발생하게 됩니다.
Stack 자료구조를 사용하면 시간을 줄일 수 있습니다.
입력받은 원소들을 왼쪽부터 오른쪽으로 이동하며 Stack에 담습니다.
동시에 현재 Stack 내의 원소들과 현재 입력 값을 비교해 작은 원소들을 출력하고 해당 값보다 작은 수를 남깁니다.
순차적으로 이동하면서 단계를 진행하면 스택 내부가 내림차순 형태로 구성 되게 되고 1번의 순회 만으로 수열을 생성해 낼 수 있습니다.
위에서 Stack에 담는 원소들은 위치 값을 포함해야 하기에 원소를 직접 담지 않고 index를 담아줍니다.

 

---

 

2. 솔루션

const fs = require('fs')
const [T, groupOfNumbersString] = fs.readFileSync(process.platform ===
                                                  'linux' ? '/dev/stdin' : 'input.txt')
                                    .toString().trim().split('\n')
const countOfCase = +T;
const groupOfNumber = groupOfNumbersString.split(' ').map(n => +n)
const stack = [];
// 정답 출력용 수열 생성 ( -1 초기화 )
const answer = Array.from({
    length: countOfCase
}, (v, k) => {
    return -1
})

// 입력의 왼쪽 ( 처음 ) 부터 진행
for (let i = 0; i < countOfCase; i++) {
    const current = groupOfNumber[i];
    // Stack이 비어있다면 비교 할 대상 없으므로 Stack에 현재 입력의 Index를 Push 하고 다음 입력으로 이동
    if (stack.length === 0) {
        stack.push(i)
    } else {
        // Stack이 비어있지 않다면
        // 현재 입력보다 큰 값을 만날 때까지 Stack을 Pop하며 나온 Index에 현재 입력 값을 입력
        while (stack.length !== 0 && groupOfNumber[stack[stack.length - 1]] <
               current) {
            const index = stack.pop()
            answer[index] = current
        }
        // 현재 입력값 Stack에 저장

        stack.push(i)
    }
}

// Stack에 남아 있다면 오큰수가 없는 것으로 판단 => -1 로 padding
while (stack.length !== 0) {
    const index = stack.pop()
    answer[index] = -1
}

console.log(answer.join(' '))

 

---

마치며

문제 풀이 시에 순차적으로 진행한다는 명제가 존재한다면 스택이나 큐를 통한 사고를 해 볼 수 있습니다.