[Algorithm]BOJ 1676 팩토리얼 0의 개수

1. 첫번째 풀이

package Algoritm.day9;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class no1676 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        long targetNum = 1;

        for(int i=1; i<=n; i++){
            targetNum *= i;
        }

        System.out.println(targetNum);

        String target = String.valueOf(targetNum);
        long zeroCount = 0;


        for(int i=target.length()-1; i>=0; i--){
            if(target.charAt(i) == '0'){
                zeroCount++;
            }else{
                System.out.println(zeroCount);
                return;
            }
        }
    }
}

팩토리얼 값을 String으로 저장해서, charAt()메소드를 이용하여 뒤에서부터 0의 개수를 카운트하려고 했다. > 작은 숫자의 경우는 오류 없이 계산이 가능하지만, 500!과 같은 팩토리얼 넘버는 '정수형'으로 받지를 못하기 때문에 애초에 targetNum에 값이 생성되지 않아서 올바른 답을 구할 수 없다.

---

2. 두번째 풀이 (통과)

• 팩토리얼을 쌩으로 구할 생각을 하면 안되는 문제인것
• 0의 개수를 구하고 싶다 > 어떤수든 n x 10k 으로 표현 될 수 있고, 그 때의 k 개수를 구하는 방향으로 수정
• 10k에서 10은 2와 5의 곱으로만 발생하기 때문에 팩토리얼 과정에서 2와 5가 몇번이 나오는지를 세서, 그 둘 중 적은 값에 맞춰주면 K값을 구할 수 있다.

package Algoritm.day9;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class no1676 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        int cnt2 = 0;
        int cnt5 = 0;

        for (int i = 1; i <= n; i++) {
            int target = i;

            while (target % 2 == 0) {
                cnt2++;
                target = target / 2;
            }

            while (target % 5 == 0) {
                cnt5++;
                target = target / 5;
            }
        }
        System.out.println(Math.min(cnt2, cnt5));
    }
}

3. n제한이 10억 이엇다면? 더 빠르게 코드를 짠다면?

• 결국 5의 배수들을 세는 게 중요한 것!
  예를 들어 500이었다면, 5x1, 5x2, 5x3 ,,,,, 5x100까지 총 100개의 5의 배수가 나온다. 이때 이 100은 타겟넘버인 500을 5로 나눈 몫이다.
  그럼 1~100까지의 숫자 중에도 5의 배수가 잇을 테니까 다시 그 개수를 세준다 그 역시 몫이다.
  (5x1, 5x2, ,,, 5x20)
  몫이 더 이상 5로 나눠지지 않을때까지 5로 나누고 그 몫들의 합을 구하면, 0의 개수를 구할 수 있다.