17298 오큰수 , 17299 오등큰수 (자바스크립트)

문제

크기가 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)을 공백으로 구분해 출력한다.

===

문제 분석

현재 검사할려는 숫자를 기준으로 오른쪽에 위치한 수들 중 현재 값보다 큰 값을 answer[현재 인덱스] 에  기록한 뒤 출력하면 되는 문제이다.

수의 범위가 1백만으로 N^2가 된다면 시간 초과가 되는 문제이므로

처음 인덱스부터 탐색을 시작하여 가장 가까운 수를 일일히 찾는 것은 불가능하다.

따라서 가장 끝에서부터 탐색을 시작하여 큰 값들을 담아둘 공간이 필요했다.

이를 위해 스택을 활용하였고 값을 비교할 때 두가지가 발생한다.

arr[현재 인덱스] 가 스택 꽁지에 있는 수보다 작을 경우 -> 해당 인덱스의 수보다 가장 큰값은 스택 꽁지가 된다.

arr[현재 인덱스] 가 스택 꽁지에 있는 수보다 큰 경우 -> 해당 인덱스의 수보다 큰 값이 나올 때까지 스택을 pop 해본다.

이때 pop 과정에서 stack의 길이가 0이 된다면 오른쪽 수중 현재 인덱스의 수보다 큰 값은 없다는 것이므로 -1을 기록해둔다.

const arr = input[1].split(' ').map((v) => +v);
const answer = Array.from({ length: n }, () => -1);
const s = [arr.at(-1)];
for (let i = n - 2; i >= 0; i--) {
    if (s.at(-1) > arr[i]) {
        answer[i] = s.at(-1);
        s.push(arr[i]);
    } else {
        while (s.length !== 0 && s.at(-1) <= arr[i]) {
            s.pop();
        }
        if (s.length === 0) {
            answer[i] = -1;
        } else {
            answer[i] = s.at(-1);
        }
        s.push(arr[i]);
    }
}

 

전체 코드

const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');

const n = +input[0];
const arr = input[1].split(' ').map((v) => +v);
const answer = Array.from({ length: n }, () => -1);
const s = [arr.at(-1)];
for (let i = n - 2; i >= 0; i--) {
    if (s.at(-1) > arr[i]) {
        answer[i] = s.at(-1);
        s.push(arr[i]);
    } else {
        while (s.length !== 0 && s.at(-1) <= arr[i]) {
            s.pop();
        }
        if (s.length === 0) {
            answer[i] = -1;
        } else {
            answer[i] = s.at(-1);
        }
        s.push(arr[i]);
    }
}
console.log(answer.join(' '));

 

===>

17299 오등큰수

이 문제는 위의 문제에서 비교군이 arr[i]가 아닌 arr[i]이 등장한 횟수들을 기준으로 동작하므로 각 인덱스의 value들이 등장한 횟수를 기록할 obj를 만들어준다.

const n = +input[0];
const arr = input[1].split(' ').map((v) => +v);
const obj = arr.reduce((acc, cur) => {
    acc[cur] = (acc[cur] || 0) + 1;
    return acc;
}, {});

 이후로는 위의 문제와 동일한 로직으로 스택에 값을 넣어주면서 비교하는 값을 arr[i]에서 obj[arr[i]로 바꿔주면 된다.

const answer = Array.from({ length: n }, () => -1);
const s = [arr.at(-1)];

for (let i = n - 2; i >= 0; i--) {
    if (obj[s.at(-1)] > obj[arr[i]]) {
        answer[i] = s.at(-1);
        s.push(arr[i]);
    } else {
        while (s.length !== 0 && obj[s.at(-1)] <= obj[arr[i]]) {
            s.pop();
        }
        if (s.length === 0) {
            answer[i] = -1;
        } else {
            answer[i] = s.at(-1);
        }
        s.push(arr[i]);
    }
}

전체 코드

const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');

const n = +input[0];
const arr = input[1].split(' ').map((v) => +v);
const obj = arr.reduce((acc, cur) => {
    acc[cur] = (acc[cur] || 0) + 1;
    return acc;
}, {});

const answer = Array.from({ length: n }, () => -1);
const s = [arr.at(-1)];

for (let i = n - 2; i >= 0; i--) {
    if (obj[s.at(-1)] > obj[arr[i]]) {
        answer[i] = s.at(-1);
        s.push(arr[i]);
    } else {
        while (s.length !== 0 && obj[s.at(-1)] <= obj[arr[i]]) {
            s.pop();
        }
        if (s.length === 0) {
            answer[i] = -1;
        } else {
            answer[i] = s.at(-1);
        }
        s.push(arr[i]);
    }
}
console.log(answer.join(' '));