구름 큰 팩토리얼

문제

팩토리얼 수학 기호는 아래와 같이 정의할 수 있다
N! = 1 x 2 x ... x N
이 때 N이 주어지면, N! 값을 출력하시오.

입력

첫째 줄에 N이 주어진다.

• 1 <= N <= 100,000

출력

N!값을 1,000,000,007값으로 나눈 나머지를 출력하시오.

---

첫번째 시도

재귀 함수를 이용하여 만들기

class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String input = br.readLine();
		int num = Integer.parseInt(input);
		num = factorial(num);
		System.out.println(num % 1000000007);
	}

	public static BigInteger factorial(int num) {
		if (num == 1) {
        	return 1;
        }

		return num * factorial(num - 1);
	}
}

문제점 발생

• int의 범위를 벗어나는 수 발생

-> 해결법 : BigInteger 사용

---

두번째 시도

BigDecimal 사용

class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String input = br.readLine();
		BigInteger num = new BigInteger(input);
		num = factorial(num);
		System.out.println(num.remainder(BigInteger.valueOf(1000000007)));
	}

	public static BigInteger factorial(BigInteger num) {
		if (num.equals(BigInteger.ONE)){
        	return BigInteger.ONE;
        }

		return num.multiply(factorial(num.subtract(BigInteger.ONE)));
	}
}

문제점 발생

• 일정 이상 크기가 넘어갈 경우 stack overflow 발생
  참고 stackOverFlowError

-> 해결법 : 메모이제이션 기법 사용
출처 Memoization 기법 사용법

---

최종 결과물

import java.io.*;
import java.math.BigInteger;
import java.util.List;
import java.util.ArrayList;

class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String input = br.readLine();
		BigInteger num = new BigInteger(input);
		num = factorial(num);
		System.out.println(num.remainder(BigInteger.valueOf(1000000007)));
	}

	public static BigInteger factorial(BigInteger num) {
		BigInteger result = BigInteger.ONE;
		
		for(int i = 1;;i++) {
			result = result.multiply(BigInteger.valueOf(i));
			
			if(num.equals(BigInteger.valueOf(i))) {
				break;
			}
		}

		return result;
	}
}