백준 1676: 팩토리얼 0의 개수(java)

문제

 

풀이

N을 입력받고 N의 팩토리얼을 구한 뒤 각 숫자를 0과 비교하여 0이 아닌 숫자가 나오기 전까지 0의 개수를 세면 되는 비교적 간단한 문제이다.

 

라고 아무 생각 없이 풀면 저처럼 됩니다

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

public class Main {
	private static int getFactorial(int n) {
		if(n==1)
			return 1;
		else
			return(n*getFactorial(n-1));
	}

	public static void main(String[] args) throws IOException{
		BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
		
		int N=Integer.parseInt(in.readLine());		
		int factorial=getFactorial(N);
		
		String factorialStr=String.valueOf(factorial);
		
		int count=0;
		for(int i=factorialStr.length()-1; i>=0; i--) {
			if(factorialStr.charAt(i)=='0')
				count++;
			else
				break;
		}
		
		System.out.println(count);
	}
}

코드는 문제가 없는 것 같은데 왜 틀렸는지 의문이었는데, 문제를 다시 읽어보니 N이 0≤N ≤500이다. 500!= 

122013682599111006870123878542304692625357434280319284219241
358838584537315388199760549644750220328186301361647714820358
416337872207817720048078520515932928547790757193933060377296
085908627042917454788242491272634430567017327076946106280231
045264421887878946575477714986349436778103764427403382736539
747138647787849543848959553753799042324106127132698432774571
554630997720278101456108118837370953101635632443298702956389
662891165897476957208792692887128178007026517450776841071962
439039432253642260523494585012991857150124870696156814162535
905669342381300885624924689156412677565448188650659384795177
536089400574523894033579847636394490531306232374906644504882
466507594673586207463792518420045936969298102226397195259719
094521782333175693458150855233282076282002340262690789834245
171200620771464097945611612762914595123722991334016955236385
094288559201872743379517301458635757082835578015873543276888
868012039988238470215146760544540766353598417443048012893831
389688163948746965881750450692636533817505547812864000000000
000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000 

이므로(너무 길어서 접음) int형을 사용할 수 없고, 대신 BigInteger를 사용하여 동일한 방식으로 다시 풀이하였다.

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

public class Main {
	private static BigInteger getFactorial(BigInteger n) {
		if(n.compareTo(BigInteger.ONE)<=0)
			return BigInteger.ONE;
		else
			return(n.multiply(getFactorial(n.subtract(BigInteger.ONE))));
	}

	public static void main(String[] args) throws IOException{
		BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
		
		int N=Integer.parseInt(in.readLine());		
		BigInteger factorial=getFactorial(BigInteger.valueOf(N));
		
		String factorialStr=String.valueOf(factorial);
		
		int count=0;
		for(int i=factorialStr.length()-1; i>=0; i--) {
			if(factorialStr.charAt(i)=='0')
				count++;
			else
				break;
		}
		
		System.out.println(count);
	}
}

BigInteger를 사용하느라 형식이 조금 달라진 것을 제외하고는 전체적인 구조는 동일하다.

(재귀함수로 팩토리얼 구하는 원리는 링크 참조)