[Node.js] BOJ - 증가 수열

백준 링크 : https://www.acmicpc.net/problem/30236

30236번: 증가 수열

 

문제

수열 
$a_{1}, a_{2}, \ldots, a_{n}$이 주어진다. 다음 조건을 만족하는 수열 
$b_{1}, b_{2}, \ldots, b_{n}$을 좋은 수열이라고 정의한다:

 
$b_{i}$는 양의 정수이다(
$i = 1, 2, \ldots, n$).
 
$b_{i} \neq a_{i}$이다(
$i = 1, 2, \ldots, n$).
 
$b_{1} < b_{2} < \ldots < b_{n}$이다.
좋은 수열 
$b_{1}, b_{2}, \ldots, b_{n}$에 대하여, 
$b_{n}$의 최솟값을 구하여라.

입력
각 입력은 여러 개의 테스트 케이스로 이루어져 있다. 첫 번째 줄에 테스트 케이스의 개수 
$t$가 주어진다(
$1 \le t \le 100$). 다음 줄부터 각각의 테스트 케이스가 주어진다.

각각의 테스트 케이스의 첫 번째 줄에 정수 
$n$이 주어진다 (
$1 \le n \le 100$).

두 번째 줄에 
$n$개의 정수 
$a_1, a_2, \ldots, a_n$이 공백으로 구분되어 주어진다 (
$1 \le a_i \le 10^{9}$).

출력
각각의 테스트 케이스마다 정답을 출력한다.

 

풀이

위 문제는 그리디 알고리즘 유형의 문제로 특정 B 수열의 인덱스의 값이 A수열의 인덱스 값과 같지 않고 각 수열의 값은 오름차순을 만족하며 양수이다 라는 기준을 부합하되 최소의 값을 구해야 하므로 b 수열의 첫번째 인덱스를 설정할때 A수열이 1보다 크다면 B수열의 첫번째 인덱스의 값은 1 아니라면 A수열의 첫번째 인덱스에서 1을 더해준 값으로 설정하여 풀이하였다.

 

코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

const t = Number(input[0]);

let line = 1;

//B수열의 다음 값을 정하는 함수
const findNum = (a, b) => {
  let num = b + 1;
  if (num == a) {
    num = findNum(a, b + 1);
  }
  return num;
};

for (let i = 0; i < t; i++) {
  let n = Number(input[line]);
  let a = input[line + 1].split(' ').map(Number);
  let b = new Array(n);

  if (a[0] - 1 > 0) { // A수열의 첫번째 값이 1보다 크다면 B수열의 첫번째 값은 1
    b[0] = 1;
  } else {  // 그게 아니라면 A수열 첫번째 값 + 1 
    b[0] = a[0] + 1;
  }

  for (let j = 1; j < n; j++) {
    let bNum = findNum(a[j], b[j - 1]);
    b[j] = bNum;
  }
  console.log(Math.max(...b));

  //다음 라인으로 이동
  line += 2;
}