자바(Java)로 숫자의 팩토리얼에서 후행 0의 개수를 세는 방법

어떤 수의 팩토리얼(계승) 결과에서 뒤에 붙는 후행 0(trailing zeroes)의 개수를 구하는 것은 알고리즘 문제에서 자주 등장하는 주제입니다. 자바(Java)로 이를 계산하는 코드는 다음과 같습니다.

예제 코드

import java.io.*;
public class Demo{
    static int trailing_zero(int num){
        int count = 0;
        for (int i = 5; num / i >= 1; i *= 5){
            count += num / i;
        }
        return count;
    }
    public static void main (String[] args){
        int num = 1000000;
        System.out.println("The number of trailing zeroes in " + num +" factorial is " +
        trailing_zero(num));
    }
}

실행 결과

The number of trailing zeroes in 1000000 factorial is 249998

코드 설명

Demo라는 이름의 클래스 안에는 trailing_zero라는 함수가 정의되어 있습니다. 이 함수는 카운트 값을 0으로 초기화한 뒤, 후행 0의 개수를 구하고자 하는 숫자를 기준으로 반복문을 수행합니다.

여기서 핵심 아이디어는 후행 0이 곱셈 과정에서 2 × 5 쌍에 의해 생성된다는 점입니다. 팩토리얼 계산에서는 2가 5보다 훨씬 많이 등장하기 때문에, 실질적으로는 숫자 5가 몇 번 곱해지는지를 세면 됩니다. 따라서 반복문은 5부터 시작하여 매번 5씩 곱해지며(i *= 5), num을 i로 나눈 몫을 카운트에 누적합니다.

예를 들어 25!의 경우, 5의 배수는 5개(5, 10, 15, 20, 25)이고 그중 25는 5를 두 번 포함하므로 후행 0은 총 6개가 됩니다. 이처럼 반복적으로 나눗셈을 수행하면 5의 거듭제곱까지 모두 고려할 수 있습니다.

계산이 완료되면 함수는 최종 카운트 값을 반환합니다. 메인(main) 함수에서는 변수 num에 원하는 숫자를 지정하고, 이 값을 인자로 전달하여 함수를 호출합니다. 마지막으로 결과와 함께 관련 메시지가 콘솔에 출력됩니다.

위 예제에서는 1,000,000의 팩토리얼에 대한 후행 0의 개수인 249998이 출력된 것을 확인할 수 있습니다. 이 방법은 단순히 팩토리얼 값을 직접 계산하지 않고도 O(log n) 시간 복잡도로 빠르게 답을 구할 수 있다는 장점이 있습니다.