[BOJ / Node.js] 17299. 오등큰수

17299번: 오등큰수

문제

크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오등큰수 NGF(i)를 구하려고 한다.

Ai가 수열 A에서 등장한 횟수를 F(Ai)라고 했을 때, Ai의 오등큰수는 오른쪽에 있으면서 수열 A에서 등장한 횟수가 F(Ai)보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오등큰수는 -1이다.

예를 들어, A = [1, 1, 2, 3, 4, 2, 1]인 경우 F(1) = 3, F(2) = 2, F(3) = 1, F(4) = 1이다. A1의 오른쪽에 있으면서 등장한 횟수가 3보다 큰 수는 없기 때문에, NGF(1) = -1이다. A3의 경우에는 A7이 오른쪽에 있으면서 F(A3=2) < F(A7=1) 이기 때문에, NGF(3) = 1이다. NGF(4) = 2, NGF(5) = 2, NGF(6) = 1 이다.

 

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.

출력

총 N개의 수 NGF(1), NGF(2), ..., NGF(N)을 공백으로 구분해 출력한다.

예제 입력 1 복사

7
1 1 2 3 4 2 1

예제 출력 1 복사

-1 -1 1 2 2 1 -1

 

Solve

[BOJ / Node.js] 17298. 오큰수

• 이전에 풀이했던 오큰수를 응용한 문제로 다음과 같이 의사코드를 작성하며 풀이했습니다.

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

• 등장한 횟수를 저장하기 위한 객체 F를 만들어 주었습니다.
• NGF 배열 생성 후 -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 stack = [];
const NGF = Array(n).fill(-1);

// 횟수를 저장하는 객체
const F = {};
arr.forEach((el)=>{
    if(!(el in F)) F[el] = 0;
    F[el]++;
})

for(let i = 0 ; i < n-1; i++) {
    const cur = arr[i]; const next = arr[i+1];

    // 바로 찾을 수 있는 경우 ?
    if(F[cur] < F[next]) {
        NGF[i] = next;

        while(stack.length) {
            const [topCur, topIndex] = stack[stack.length-1];
            if(F[topCur] < F[next]) {
                NGF[topIndex] = next;
                stack.pop();
            }
            else break;
        }
    } else {
        stack.push([cur, i]);
    }
}

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