[백준] 1676 팩토리얼 0의 개수_ JAVA

● 문제

---

● 풀이

 

10! = 10×9×8×...×2×1 = 3,628,800

 

뒤에서부터 8 전까지 0의 개수가 2개이므로 출력은 2이다.

 

내가 생각한 풀이는

팩토리얼 값을 구한뒤 문자열로 변환해서 뒤에서부터 문자열이 0이면 카운트 세는 것이다.

---

첫번째 풀이 ( 오류 )

이유 : int값으로 팩토리얼 계산 값을 받아왔는데, 특정 이상 수의 값이 int 범위를 초과한다.

해결 방법 : BigInteger 클래스 사용

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int N = in.nextInt();

        String num = Integer.toString(factorial(N));

        int cnt = 0;

        //num의 인덱스는 0부터 시작하므로 가장 오른쪽 문자의 인덱스는 num.length()-1 이다.
        for(int i = num.length()-1; i >= 0; i--){
            if(num.charAt(i) == '0'){
                cnt ++;
            }else
                break;
        }
        System.out.println(cnt);

    }
    static int factorial(int n){
        if (n == 1 || n == 0)
            return 1;
        return n * factorial(n-1);
    }
}

---

두 번째 풀이 (성공)

위에서 오류를 잡아 BigInteger 클래스를 사용하여 코드를 변환하였다.

백준 풀이는 성공하였지만, 이 코드의 문제는 입력 값이 커질 경우 스택 오버플로우가 발생할 수도 있다는 점이다.

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int N = in.nextInt();

        BigInteger factorial = factorial(N);
        String num = factorial.toString();

        int cnt = 0;

        for (int i = num.length() - 1; i >= 0; i--) {
            if (num.charAt(i) == '0') {
                cnt++;
            } else {
                break;
            }
        }
        System.out.println(cnt);
    }

    static BigInteger factorial(int n) {
        if (n == 0 || n == 1) {
            return BigInteger.ONE;
        }
        return BigInteger.valueOf(n).multiply(factorial(n - 1));
    }
}

---

그래서 더 최적화된 코드를 찾기 위해 구글링을 해보았다.

(출처 : https://st-lab.tistory.com/165)

 

매우 간단한 코드가 있었다.... 박탈감이 든다........

import java.util.Scanner;
 
public class Main {
 
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
 
		int num = in.nextInt();
		int count = 0;
 
		while (num >= 5) {
			count += num / 5;
			num /= 5;
		}
		System.out.println(count);
	}
 
}

 코드 설명

위 팩토리얼를 보면 규칙이 있다.

 

뒷자리가 0이 나오는 경우는 2와 5가 곱해져 있을 때이고, 거꾸로 말하자면 소인소분해를 해서 2와 5가 존재할 경우 0으로 끝나는 것이다.

위 표를 보면 5의 배수마다 0의 카운트 값이 증가하는 것을 볼 수 있다.

 

그런데 25일 때 카운트값이 1이 아닌 2가 증가한다.

그래서 단순히 5로 나누는 것이 아니라 반복문을 통해 5로 나누면서 누적합을 해주어야한다.