백준 9009번 Node.js 풀이

문제 링크

- 내 풀이

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

const N = Number(input[0]);

let numArr = [];

let answer = [];

for (let i = 1; i <= N; i++) {
  numArr.push(Number(input[i]));
}

function makeFibonacciArr(number) {
  const fib = [0, 1];

  while (fib[fib.length - 1] < number) {
    const sum = fib[fib.length - 1] + fib[fib.length - 2];

    fib.push(sum);
  }

  return fib;
}

for (let j = 0; j < N; j++) {
  let number = numArr[j];
  let arr = [];

  const fibonacciArr = makeFibonacciArr(number);
  let fibIndex = fibonacciArr.length - 1;

  while (number > 0) {
    if (number - fibonacciArr[fibIndex] >= 0) {
      arr.push(fibonacciArr[fibIndex]);
      number -= fibonacciArr[fibIndex];
    }
    fibIndex--;
  }

  answer.push(arr);
}

answer.forEach((answer) => console.log(answer.sort((a, b) => a - b).join(" ")));

반복문을 돌면서 해당 숫자까지의 피보나치 숫자를 담은 배열을 만들어준다.

그 후에 해당 숫자에서 피보나치 배열의 마지막값(해당 피보나치 배열에서 가장 큰수) 를 빼줬을때 0보다 크다면 해당 값을 반복문안의 배열에 넣어준다.

여기서 숫자가 10억이어서 시간복잡도를 신경써야하나? 라고 생각할수도 있는데, 테스트 케이스가 10억개가 아니고 그냥 각 숫자가 10억이라는 제한이어서 시간복잡도는 굳이 신경쓰지 않아도 됐다.