[201] 17298번 오큰수

younoah·2021년 11월 13일

172098 JavaScript boj 백준 자바스크립트

[백준-기초]

목록 보기

10/29

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 복사

4
3 5 2 7

예제 출력 1 복사

5 7 7 -1

예제 입력 2 복사

4
9 5 4 8

예제 출력 2 복사

-1 8 8 -1

try1

//---- 세팅 ----//
const fs = require('fs');
const stdin = (
  process.platform === 'linux'
    ? fs.readFileSync('/dev/stdin').toString()
    : `\
4
9 5 4 8
`
).split('\n');

const input = (() => {
  let line = 0;
  return () => stdin[line++];
})();

//---- 풀이 -----//
const n = Number(input());
const arr = input().split(' ').map(Number);
const res = [];

for (let i = 0; i < n - 1; i++) {
  let tmp = -1;
  for (let j = i + 1; j < n; j++) {
    if (arr[j] > arr[i]) {
      tmp = arr[j];
      break;
    }
  }
  res.push(tmp);
}
res.push(-1);
console.log(res.join(' '));

처음엔 스택을 활용하지 않고 단순히 이중 반복문을 도는 간단한 로직으로 구현하였다.

처음부터 n-1까지 돌면서 하나씩 오른쪽에 있는 모든 값들과 비교해서 처음으로 발견된 큰수를 res에 푸쉬한다. (마지막은 항상 -1이고 구현의 편의성을 위해 n-1까지 순회)

n-1까지만 순회하였고 항상 마지막은 -1이기 때문에 반복문이 끝나고 -1을 푸쉬한다.

하지만 시간초과

try2

//---- 세팅 ----//
const fs = require('fs');
const stdin = (
  process.platform === 'linux'
    ? fs.readFileSync('/dev/stdin').toString()
    : `\
4
9 5 4 8
`
).split('\n');

const input = (() => {
  let line = 0;
  return () => stdin[line++];
})();

//---- 풀이 -----//
const n = Number(input());
const arr = input().split(' ').map(Number);
const res = [];

while (arr.length > 0) {
  const now = arr.shift();
  let nge = -1;
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] > now) {
      nge = arr[i];
      break;
    }
  }
  res.push(nge);
}

console.log(res);

이번엔 입력 받은 배열을 스택처럼 앞에서 하나씩 뽑아서 남은 배열에서 값을 하나씩 비교하는 방식으로 구현했다.

하지만 이번에도 시간초과가 나왔다.

배열의 크기가 최대 100만이다보니 역시 2중 반복문은 무리인듯 싶다.

근데 왜 try1에서는 시간초과가 아닌 실패일까?? 아마 시간초과 케이스 이전에 로직이 잘못되서 틀린것 같다.

최종 코드

//---- 세팅 ----//
const fs = require('fs');
const stdin = (
  process.platform === 'linux'
    ? fs.readFileSync('/dev/stdin').toString()
    : `\
4
3 5 2 7
`
).split('\n');

const input = (() => {
  let line = 0;
  return () => stdin[line++];
})();

//---- 풀이 -----//
const n = Number(input());
const arr = input().split(' ').map(Number);
const res = Array(n).fill(-1);
const stack = [];

for (let i = 0; i < n; i++) {
  while (stack.length > 0 && stack[stack.length - 1][0] < arr[i]) {
    const [value, idx] = stack.pop();
    res[idx] = arr[i];
  }
  stack.push([arr[i], i]);
}

console.log(res);