[알고리즘 PS] 백준 10872 팩토리얼 자바 문제 풀이

문제

해당 포스팅은 백준의 10872번 팩토리얼 의 접근과 해결 방법을 설명한 글 입니다.
정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.

문제

예제 입력 & 출력

해결법

이 문제는 재귀 호출의 예에서도 봤듯, 가장 기초적인 문제이다.

혹시 모르니 문제의 조건에 대해서 주의해서 봐보자.

시간 복잡도

시간 복잡도는 n이 최대 12이며 재귀를 n번 수행하는데, 여기서 재귀로 들어갔을 때 단순 if 검증문과 내부 재귀를 호출하는 단순한 구조 이므로 o(n)이라는 복잡도가 나온다.

그럼 o(12) 이므로 1초 내에 충분히 수행할 수 있을 것으로 보인다.

입력 자료형

입력은 12 까지이며 예제 입력에 보면 10!이 300만이라고 한다. 그럼 대충 12!은 3억 ~ 4억 쯤이 될 것이다.

int 자료형은 정수를 최대 21억을 표현할 수 있기 때문에 충분히 12!을 커버할 수 있다.

종료 조건

재귀함수에서는 종료 조건이 빠지면 성능 저하를 아주 직격으로 맞게된다.

그러므로 종료 조건이 필수인데, 팩토리얼 함수에서 1!은 1이므로 1을 만나면 종료한다는 조건을 추가해줄 수 있다.

꼭 주의해야할 오답 후보

여기 문제에서 0보다 크거나 같은 정수라고 했다.

크거나 같은.

그럼 0이 들어올 수 있는데, 만약 0이 들어온다면 최초 호출이 아마 factorial(0)이 된다. 그럼 이를 내부적으로 본다면 0 * factorial(-1) -1 * factorial(-2) ...을 호출하게 되고 StackOverFlow를 발생시킬 수 있다.

그러므로 입력이 0일 때 종료 조건을 하나 더 추가시켜야 한다.

정답 코드

import java.io.*;

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(String.valueOf(factorial(n)));

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

  private static int factorial(int n) {
    if(n == 0 || n == 1) return 1; // 종료 조건
    return n * factorial(n-1);
  }
}

---

정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.