[백준 BOJ] 1676 - 팩토리얼 0의 개수 (node.js)

acmicpc- 팩토리얼 0의 개수 (node.js)

byseop · 2022년 11월 25일

[백준 BOJ] 1676 - 팩토리얼 0의 개수 (node.js)

 

문제

N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500)

출력

첫째 줄에 구한 0의 개수를 출력한다.
 
 

풀이

팩토리얼은 기하급수적으로 숫자가 늘어나는 특징이 있다. 자바스크립트에서 일반적인 수의 계산으로는 풀 수 없는 문제였다. (실제로 그냥 풀어버림)
잠시 30! 까지의 수를 확인해보자.
  0! = 1
  1! = 1
  2! = 2
  3! = 6
  4! = 24
  5! = 120
  6! = 720
  7! = 5040
  8! = 40320
  9! = 362880
 10! = 3628800
 11! = 39916800
 12! = 479001600
 13! = 6227020800
 14! = 87178291200
 15! = 1307674368000
 16! = 20922789888000
 17! = 355687428096000
 18! = 6402373705728000
 19! = 121645100408832000
 20! = 2432902008176640000
 21! = 51090942171709440000
 22! = 1124000727777607680000
 23! = 25852016738884976640000
 24! = 620448401733239439360000
 25! = 15511210043330985984000000
 26! = 403291461126605635584000000
 27! = 10888869450418352160768000000
 28! = 304888344611713860501504000000
 29! = 8841761993739701954543616000000
 30! = 265252859812191058636308480000000
숫자가 피라미드처럼 쌓이면서 기하급수적으로 늘어난다. 자바스크립트에서 이러한 연산을 하기 위해서는 BigInt 를 이용하여야 한다. 자세한 설명은 MDN BigInt 에서 ㅎㅎㅎ
 

정답

const fs = require('fs');
const inputData = fs.readFileSync('/dev/stdin').toString().trim();

function factorial(n) {
  return n ? BigInt(BigInt(n) * BigInt(factorial(n - 1))) : 1;
}

const solution = (n) => {
  const fArr = [...(factorial(n)).toString()];
  let result = 0;
  while(true) {
    const cur = fArr.pop();
    if (cur === '0') { 
      result += 1;
    }
    else break;
  }
  return result
}

console.log(solution(Number(inputData)));
간단히 BigInt 로 팩토리얼 값을 구한 다음에, 뒤에서부터 0의 갯수를 세야하기때문에 배열에 넣고 pop 으로 한개씩 빼면서 값을 확인하고 0이면 result 를 늘리고 아니면 break 한다.