[BOJ/백준] 27434번 : 팩토리얼 3 (Java)

27434번 : 팩토리얼 3 (https://www.acmicpc.net/problem/27434)

---

문제

---

접근 방법

---

첫 번째 접근 (시간 초과)

• 처음에는 N의 최댓값이 100,000이고 반복문으로 구하면 시간복잡도가 O(N)이니까 시간 제한 4초 이내로 해결할 수 있을 줄 알았다.

• 그러나 실제로 해보니까 시간도 초과되었고 공간복잡도도 너무 큰 것 같았다.

• 코드를 생각해보니 BigInteger 클래스를 사용하여 연산하는 부분이 오래 걸리는 것 같았다.

  • 찾아보니까 BigInteger 클래스는 일반적인 연산보다 속도가 느리고 특히 multiply 메서드의 경우 연산에 사용된 BigInteger 크기에 따라 시간이 더 걸릴 수 있다고 한다.
  • 따라서 실질적인 시간복잡도는 O(N \* k)로, 여기서 k는 BigInteger의 multiply 연산의 시간복잡도이다.
  • 메모리도 초과할 수 있다고 한다.

두 번째 접근 (성공)

• 두 번째 접근은 검색을 해서 나온 방법인 분할 정복을 사용한 방법이다.

• 주어진 팩토리얼의 범위 1~N을 반으로 나누고, 각각의 범위를 다시 재귀적으로 계산하여 결과를 곱한다.

• 이 방법은 전체적으로 N에 대해 logN 단계의 재귀 호출이 발생하기 때문에 O(NlogN)의 시간복잡도를 가진다.

코드

---

접근 1 - 반복문(실패)

import java.io.*;
import java.math.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		BigInteger factorial = BigInteger.ONE;
		for (int i = 2; i <= N; i++) {
			factorial = factorial.multiply(BigInteger.valueOf(i));
		}
		System.out.println(factorial);
		br.close();
	}
}

위의 코드의 결과

접근 2 - 분할 정복(성공)

import java.io.*;
import java.math.*;

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());
		bw.write(factorial(1, N).toString());
		bw.flush();
		bw.close();
		br.close();
	}

	public static BigInteger factorial(int start, int end) {
		BigInteger ret = BigInteger.valueOf(start);
		if (start < end) {
			int tmp = (start + end) / 2;
			ret = factorial(start, tmp).multiply(factorial(tmp + 1, end));
		}
		return ret;
	}
}

위의 코드의 성능

배운 점 메모

---

알고리즘을 고를 때 입력값의 범위와 시간복잡도에 대해서만 생각하는데, 이론적인 시간복잡도만 생각하는 게 아니고 코드에서 사용된 클래스 등 전체적인 실행 흐름도 고려해 봐야 한다는 것을 알게 되었다.

(자바로는 반복문으로 풀면 시간 초과가 발생했는데 브론즈 5인 것을 보면 다른 언어로는 반복문으로도 풀 수 있을지도 모르겠다고 생각했다.)