[Java] 백준알고리즘 #1676 팩토리얼 0의 개수

백준알고리즘 #1676 팩토리얼 0의 개수 문제

입력받은 n값으로 n!의 값을 구한 후 뒤에서부터 연속된 0이 몇개 있는지 찾는 문제이다.

 

가장 먼저 생각나는 방법으로는 팩토리얼 값을 구한 후 차례로 10으로 나누어 나머지가 0이라면 count변수를 증가시켜 0의 개수를 찾는 방법이 있다.

public class Back1676 {

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

		int n = sc.nextInt();
		long fact = 1;
		int count = 0;

		for (int i = 1; i <= n; i++) {
			fact *= i;
		}
		
		while (fact > 0) {
			if (fact % 10 == 0) {
				count++;
				fact = fact / 10;
			} else
				break;
		}
		System.out.println(count);
        
		sc.close();

	}

}

다만 이렇게 코드를 짜버리게 되면 n이 21이 되는 시점부터는 long형으로도 담을 수 없는 크기의 숫자가 나오기때문에 오버플로우가 발생하게 된다.

따라서 조금 다른 방법으로 접근할 필요가 있다.

 

어떤 수의 맨 뒷자리가 0이라는 말은 10으로 나누어 떨어진다는 말인데 이는 2와 5로 소인수분해가 된다.

즉 어떤 수를 소인수분해 했을때 2와 5가 하나씩 있을 때마다 가장 뒤에 0이 붙는다는 말이 된다.

팩토리얼은 1부터 n까지의 수를 곱하는 것이므로 1부터 n까지의 수를 각각 소인수분해하여 2와 5가 몇개씩 있는지 확인한 후 이를 이용하여 뒤에오는 0의 수를 판별할 수 있다.

 

완전히 소인수분해할 필요 없이 2와 5가 있는가만 찾으면 된다.

먼저 for문을 이용하여 1부터 n까지의 수를 차례대로 비교하여 2와 5로 나누어떨어지는지 확인한 후 count2, count5를 증가시켜준다.

int count2 = 0;
int count5 = 0;
int tmp;
int count0 = 0;

for (int i = 1; i <= n; i++) {
	tmp = i;
	while (tmp % 2 == 0 || tmp % 5 == 0) {
		if (tmp % 2 == 0) {
			count2++;
			tmp = tmp / 2;
		}
		if (tmp % 5 == 0) {
			count5++;
			tmp = tmp / 5;
		}
		
	}
}

 

이제 2와 5의 개수를 찾았으니 한쌍씩 -1 할 때마다 0의 개수를 증가시켜준다.

while (true) {
	if (count2 > 0 && count5 > 0) {
		count2--;
		count5--;
		count0++;
	} else
		break;
}

 

 

이 count0을 출력하면 완성.

 

전체 코드를 보면 다음과 같다.

import java.util.Scanner;

public class Back1676 {

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

		int n = sc.nextInt();
//		long fact = 1;
//		int count = 0;
//
//		for (int i = 1; i <= n; i++) {
//			fact *= i;
//		}
//		
//		while (fact > 0) {
//			if (fact % 10 == 0) {
//				count++;
//				fact = fact / 10;
//			} else
//				break;
//		}
//		System.out.println(count);

		int count2 = 0;
		int count5 = 0;
		int tmp;
		int count0 = 0;
		for (int i = 1; i <= n; i++) {
			tmp = i;
			while (tmp % 2 == 0 || tmp % 5 == 0) {
				if (tmp % 2 == 0) {
					count2++;
					tmp = tmp / 2;
				}
				if (tmp % 5 == 0) {
					count5++;
					tmp = tmp / 5;
				}

			}
		}

		while (true) {
			if (count2 > 0 && count5 > 0) {
				count2--;
				count5--;
				count0++;
			} else
				break;
		}
		System.out.println(count0);

		sc.close();

	}

}