백준 BAEKJOON | 1676 - 팩토리얼 0의 개수JavaScript

chaen·2025년 4월 11일

JS 알고리즘 문제 풀이

목록 보기

58/62

github 문제 풀이 코드

📌 문제

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

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

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

🧩 문제 개요

자연수 N이 주어졌을 때, N! (팩토리얼)의 결과 값에서 맨 뒤에 연속된 0의 개수를 구하는 문제입니다.

예를 들어, 25!의 값은 다음과 같습니다:

25! = 15511210043330985984000000

→ 결과적으로 뒤에 6개의 0이 존재합니다.

💻 solution1

팩토리얼을 직접 계산한 후 10으로 나누기

let factorial = Array.from({length: input}, (_, i) => i + 1).reduce((acc, cur) => acc * cur, 1);
let result = 0;

while (true){
    if (factorial % 10 === 0){
        result++;
        factorial = factorial / 10;
    } else break;
}

console.log(result);

⚠️ 문제점

자바스크립트는 number 타입이 64비트 부동소수점(IEEE-754)으로 동작함
21! 이상부터는 정밀도가 깨져 뒤에 정확한 0의 개수를 구할 수 없음
큰 수에서는 factorial % 10 === 0이 잘못된 결과를 줄 수 있음

❌ 결론: 이 방식은 소수점 오차로 인해 정확하지 않음

💻 solution2

수학적으로 5의 개수 세기

let result = 0;
let divisor = 5;

while (input >= divisor) {
  result += Math.floor(input / divisor);
  divisor *= 5;
}

console.log(result);

💡 핵심 아이디어

뒤 0이 생기는 조건은 10 = 2 × 5이지만, 2는 항상 충분히 있음
따라서 5가 몇 번 곱해졌는지만 세면 됨
예: 25!이면 → 25/5 + 25/25 = 5 + 1 = 6개의 0

✅ 장점

N <= 100,000에서도 매우 빠르고 정확하게 동작
정수 연산만 사용 → 소수점 오차 없음

💻 solution3

반복문으로 5의 거듭제곱을 이용해 누적 계산

let n: number = +input; // Number(input)
let count: number = 0;

for (let i = 5; i <= n; i *= 5) {
  count += Math.floor(n / i);
}

console.log(count);

📌 설명

이 방식은 방법 2의 수학적 원리를 그대로 구현한 반복문입니다
i = 5, 25, 125, ...로 증가하며 n을 나눠 누적
5의 거듭제곱이 몇 번 나오는지 합산해서 정확한 0의 개수를 구함

📊 정리 비교

항목	방법 1: 직접 곱하고 나누기	방법 2: 수학 공식 기반	방법 3: 반복문 공식화
정확도	❌ 부동소수점 오차 발생	✅ 완전 정확	✅ 완전 정확
속도	느림 (O(N))	매우 빠름 (O(log N))	매우 빠름 (O(log N))
구현 난이도	간단하지만 위험	약간의 수학 필요	매우 직관적
권장 여부	❌ 사용 X	✅ 적극 추천	✅ 적극 추천