[JAVA] 백준 1676번

1676번 - 팩토리얼 0의 개수

 

- 틀린 문제풀이 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.math.BigInteger;

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		BigInteger bigN = new BigInteger(br.readLine());

		bigN = factorial(bigN);

		String num = bigN.toString();
		int zeroCount = 0; // 0의 개수

		for (int idx = num.length() - 1; idx >= 0; idx--) {

			if (num.charAt(idx) == '0') {
				zeroCount++;
			} else {
				bw.write(String.valueOf(zeroCount));
				break;

			}
		}

		bw.flush();
		bw.close();
	}

	private static BigInteger factorial(BigInteger bigN) {

		if (bigN.equals(new BigInteger("1"))) {
			return bigN;
		} else {
			return bigN.multiply(factorial(bigN.subtract(new BigInteger("1"))));
		}

	}

}

 

- 정답 문제풀이 

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

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

		int zeroCount = 0; // 0의 개수

		for (int i = 1; i <= N; i++) { // 5의 배수인 경우에만 0이 생김

			if (i % 125 == 0) { // 5의 세제곱
				zeroCount = zeroCount + 3;
			} else if (i % 25 == 0) { // 5의 제곱
				zeroCount = zeroCount + 2;
			} else if (i % 5 == 0) {
				zeroCount++;
			}
		}

		bw.write(String.valueOf(zeroCount));
		bw.flush();
		bw.close();
	}

}

 

처음 문제에 접근한 방식 (오답)

1. 500! 까지 계산할경우 일반적인 int, long 자료형범위초과 되므로 BigInteger 클래스를 이용하여 값을 구함

2. 구한 수를 문자열로 변환후 반복문을 통해 0의 개수를 계산

3. 0의 개수를 입력후 출력

 

정답을 맞춘 풀이방법

1 . 0은 10의 배수 즉 2 * 5 가 생길 경우에만 생성됨

2.  최종적으로 팩토리얼에 포함된 5의 개수만큼의 0이 생김

3.  구한 0의 개수를 입력후 출력