[JAVA] 백준 27433. 팩토리얼 2

이 글은 읽는데 약 3분이 걸립니다.

※개인 공부 목적의 정리글입니다.
이 글의 내용이 최선의 해답은 아닐 수 있습니다.

문제

0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N(0 ≤ N ≤ 20)이 주어진다.

출력

첫째 줄에 N!을 출력한다.

풀이

주어진 수의 팩토리얼을 구하는 매우 간단한 문제이다. 이것을 단순 반복문을 이용한 방식과 재귀함수를 이용하는 방식으로 풀어보겠다.

주의할 점은 20의 팩토리얼처럼 정답이 int의 범위를 벗어나는 큰 수일 수 있으므로 int 대신 long을 사용한다.

반복문 이용

int N = Integer.parseInt(br.readLine());
long result = 1;

for(int i=1; i<=N; i++){
    result *= i;
}

// 정답은 result에 저장됨

반복문으로 부터 N까지 곱하는 방식이다. 설명이 더 필요한가?

재귀함수 이용

public static void main(String[] args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder sb = new StringBuilder();

    long N = Long.parseLong(br.readLine());  // int로 받아도 됨
        
    if(N < 2){  // 0과 1의 팩토리얼은 1이다
        sb.append(1);
    }else{  // 2이상의 수에대해 팩토리얼 계산
        sb.append(fact(N, N-1));  // N과 N-1을 넘겨준다
    }
        
    System.out.println(sb.toString());
    br.close();
}
    
public static long fact(long a, long b){
    if(b != 1){  // 두 번째 수가 1이 아니면
        return fact(a * b, b - 1);  // 두 수를 곱하고 b-1을 넘긴다
    }else{
        return a * b;  // b가 1이면 더 줄일 필요 없으므로 두 수 곱해서 리턴
    }
}

재귀함수에 대한 기초적인 이해는 있다고 가정하고 설명하겠다. 또한 구현 방식에 따라서 위 코드의 방식과는 다르게도 구현이 가능하다.

N!을 구하기 위해서 N부터 1까지 수를 곱해가는데, 이 때 재귀 함수를 쓴다. 일단 시작되는 두 수 N과 N-1을 넘겨준다.

두 수를 곱한 결과와 N-1보다 1 작은 수를 또 넘겨준다…

이걸 반복하다 보면 두 번째 수가 호출될 때마다 1씩 줄어들다가 결국 1이 되는데, 이러면 더이상 수를 줄일 필요가 없으므로(N부터 1까지 계산을 다 했으므로) 그냥 두 수를 곱해서 리턴한다.

영상으로 나타내면 이런 식이다. 계속 호출하면서 두 수를 곱하다가 마지막 곱하기가 끝나면 그 값이 계속 리턴되면서 결국 최초에 호출한 함수에서 계산 결과가 리턴되는 식이다.

댓글