[이진 탐색] 백준 11687번 팩토리얼 0의 개수 자바(Java)

https://www.acmicpc.net/problem/11687

11687번: 팩토리얼 0의 개수

문제

가장 끝의 0의 개수가 M개인 N! 중에서 가장 작은 N을 찾는 프로그램을 작성하시오.

입력

첫째 줄에 M (1 ≤ M ≤ 100,000,000)이 주어진다.

출력

가장 끝의 0의 개수가 M개인 N! 중에서 가장 작은 N을 출력한다. 그러한 N이 없는 경우에는 -1을 출력한다.

코드

import java.util.Scanner;

public class No11687 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int M = sc.nextInt(); //0의 개수
        System.out.println(binarySearch(M, 1, 1000000000));
    }

    public static int binarySearch(int key, int left, int right) {
        boolean check = false;
        while (left <= right) {
            int mid = (left + right) / 2;    // 중간위치
            if (key < findZero(mid)){
                right = mid - 1;
            }
            else if (key == findZero(mid)){
                right = mid - 1;
                check = true;
            }
            else {
                left = mid + 1;
            }
        }
        if(check)
            return left;
        else
            return -1; // 값이 존재 하지 않을때
    }

    public static int findZero(int mid){  //0의 개수
        int count=0;

        for(int i=5; i<=mid; i*=5){
            count+=(mid/i);
        }
        return count;
    }
}

풀이

끝에 0이 나오기 위해서는 숫자에 2x5가 포함되어있어야 한다.

이때, 5의 배수가 한번 나올때 2의 배수는 2번 이상 나오기 때문에 신경쓰지 않아도 되기 때문에

포함되어있는 5의 개수 == 0의 개수이다

주의할 점은 5!, 10!, 15!와 같은 배수는 0이 하나씩 증가하지만 25!, 125!, 625!과 같이 5의 n승 값인 배수는 5가 n개 만큼 곱해지는 것이기 때문에 0이 n개만큼 증가한다는것을 고려 하여 설계 해야한다.

위에 설명한 것을 코드로 표현하면 아래와 같이 나온다.

public static int findZero(int mid){
    int count=0;

    for(int i=5; i<=mid; i*=5){
        count+=(mid/i);
    }
    return count;
}

그리고 이진 탐색을 이용하여 탐색을 하면 N값을 찾을 수 있다.

이진 탐색 코드&방법

아래에 있는 링크에 설명되어 있음

https://seaotter.tistory.com/21

[이진 탐색] 이진탐색 방법 & 자바 코드