문제 소개
정수 n이 주어졌을 때, n!(팩토리얼) 값의 끝에서 연속해서 붙는 0, 즉 후행 0(trailing zeroes)의 개수를 반환하는 함수를 작성해야 합니다.
예를 들어 다음과 같습니다.
trailingZeroes(4) = 0
trailingZeroes(5) = 1 // 5! = 120
trailingZeroes(6) = 1
4! = 24는 0으로 끝나지 않으므로 후행 0이 없고, 5! = 120처럼 0으로 끝나는 경우 그 개수를 세면 됩니다. 5!와 6! 모두 120으로 끝나므로 후행 0은 각각 1개입니다.
핵심 아이디어: 5의 인수 개수 세기
후행 0은 곱셈 과정에서 10이 몇 번 만들어지는지에 따라 결정됩니다. 10은 2 × 5로 이루어져 있기 때문에, n!을 소인수분해했을 때 2와 5가 한 쌍씩 짝지어질 때마다 후행 0이 하나씩 생깁니다.
n!에는 5보다 2가 훨씬 많이 포함되어 있으므로, 사실상 5의 개수만 세면 충분합니다. 5의 배수마다 5가 하나씩 추가되고, 25의 배수에서는 두 개씩, 125의 배수에서는 세 개씩 추가됩니다.
따라서 후행 0의 개수는 아래 공식으로 계산할 수 있습니다.
floor(n/5) + floor(n/25) + floor(n/125) + ...
구현 예제
const num = 17;
const findTrailingZeroes = num => {
let cur = 5, total = 0;
while (cur <= num) {
total += Math.floor(num / cur);
cur *= 5;
};
return total;
};
console.log(findTrailingZeroes(num));
console.log(findTrailingZeroes(5));
console.log(findTrailingZeroes(1));
코드 설명
변수 cur는 현재 확인 중인 5의 거듭제곱(5, 25, 125, ...)을 나타냅니다. 반복문 안에서 num을 cur로 나눈 몫을 total에 누적하고, cur를 5배씩 늘려가며 num 이하일 동안 반복합니다. 이 방식은 시간 복잡도 O(log₅ n)으로 매우 효율적이며, n이 아무리 커도 실제 팩토리얼 값을 직접 계산하지 않고도 답을 빠르게 구할 수 있습니다.
출력 결과
콘솔에 표시되는 출력은 다음과 같습니다.
3
1
0
- 17!: 17 ÷ 5 = 3이므로 후행 0은 3개입니다.
- 5!: 5 ÷ 5 = 1이므로 후행 0은 1개입니다 (5! = 120).
- 1!: 1 ÷ 5 = 0이므로 후행 0은 없습니다 (1! = 1).