[백준 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
한다.