[boj] 17299. 오등큰수

[boj] 17299. 오등큰수

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

17299번: 오등큰수

크기가 $ N $ 인 수열 $ A = A_1, A_2, ..., A_N $이 있다. 수열의 각 원소 $ A_i $에 대해서 오등큰수 $ NGF(i) $를 구하려고 한다.
$ A_i $가 수열 $ A $에서 등장한 횟수를 $ F(A_i) $라고 했을 때, $ A_i $의 오등큰수는 오른쪽에 있으면서 수열 $ A $에서 등장한 횟수가 $ F(A_i) $보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오등큰수는 -1이다.
예를 들어, $ A = [1, 1, 2, 3, 4, 2, 1] $인 경우 $ F(1) = 3, F(2) = 2, F(3) = 1, F(4) = 1 $이다. $ A_1 $의 오른쪽에 있으면서 등장한 횟수가 3보다 큰 수는 없기 때문에, $ NGF(1) = -1 $이다. $ A_3 $의 경우에는 $ A_7 $이 오른쪽에 있으면서 $ F(A_3=2) < F(A_7=1) $ 이기 때문에, $ NGF(3) = 1 $이다. $ NGF(4) = 2, NGF(5) = 2, NGF(6) = 1 $ 이다.

---

 

1. 문제 분석

각 수를 기준으로 해당 수보다 오른쪽에 있는 수들 중 등장 횟수가 해당 수 보다 많은 가장 왼쪽에 있는 수를 찾는 문제입니다.
원시적으로 각 원소마다 오른쪽에 있는 수를 비교 검사하는 방법이 있습니다.
수열의 크기가 1,000,000 이기 때문에 단순 반복은 시간 초과가 발생합니다.
Stack 자료구조를 사용하면 시간을 줄일 수 있습니다.
우선 자신을 인덱스로 하는 배열을 선언 후  등장 횟수를 세어 저장합니다.
입력받은 원소들을 왼쪽부터 오른쪽으로 이동하며 Stack에 담습니다.
동시에 현재 Stack 내의 원소들 각각의 등장 횟수와 현재 입력 값의 등장 횟수를 비교해 작은 원소들을 출력하고 해당 값보다 작은 수를 남깁니다.
순차적으로 이동하면서 단계를 진행하면 스택 내부가 내림차순 형태로 구성 되게 되고 1번의 순회 만으로 수열을 생성해 낼 수 있습니다.
위에서 Stack에 담는 원소들은 위치 값을 포함해야 하기에 원소를 직접 담지 않고 index를 담아줍니다.

 

---

 

2. 솔루션

const fs = require('fs')
const [T, numbersString] = fs.readFileSync(process.platform ===
                                           'linux' ? '/dev/stdin' : 'input.txt')
                             .toString().trim().split('\n')
// 입력 받은 수의 개수
const countOfNumbers = +T
// 입력 받은 수 배열
const groupOfNumbers = numbersString.split(' ').map(n => +n)
// 입력 받은 수 중 최대값
const max = Math.max(...groupOfNumbers)
// 내림차순 정렬 위한 스택
const stack = []
// 출력 배열
const answer = Array.from({
    length: countOfNumbers
}, (v, k) => -1)
// 입력 받은 수들의 등장 횟수를 담는 배열
const countOfAppearances = Array.from({
    length: max + 1
}, (v, k) => 0)
// 입력 받은 수들의 등장 횟수
for (let i = 0; i < countOfNumbers; i++) {
    countOfAppearances[groupOfNumbers[i]] += 1
}
for (let i = 0; i < countOfNumbers; i++) {
    // 현재 위치의 수가 스택 안에 있는 수들보다 등장 횟수가 큰 경우 스택 내부 원소들의 인덱스에 차례로 현재 위치의 수 입력
    while (stack.length !== 0 &&
           countOfAppearances[groupOfNumbers[stack[stack.length - 1]]] <
           countOfAppearances[groupOfNumbers[i]]) {
        const index = stack.pop()
        answer[index] = groupOfNumbers[i]
    }
    // 현재 위치의 수의 인덱스 Stack에 저장
    stack.push(i)
}

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

 

---

마치며

문제 풀이 시에 순차적으로 진행한다는 명제가 존재한다면 스택이나 큐를 통한 사고를 해 볼 수 있습니다.
앞서 포스팅했던 유사한 문제를  소개하며 포스트를 마치도록 하겠습니다

[boj] 17298. 오큰수