I am visible

homepage

contact

contents

home > algorithm > baekjoon > [baekjoon] 팩토리얼 2 (백준 27433 java 풀이)

[baekjoon] 팩토리얼 2 (백준 27433 java 풀이)
algorithm 2024-11-29 - -
algorithm baekjoon step21

intro : 재귀함수는 내가 제일 싫어하는데, 드디어 하기싫은 Chapter 들이 등장하는군.

백준 문제링크

문제

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

입력

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

출력

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

문제 풀이 (104ms)

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        // 입출력을 위한 BufferedReader, BufferedWriter, StringBuilder 객체 생성
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        // 재귀함수 factorial 메서드 실행
        long result = factorial(Integer.parseInt(br.readLine()));
        // 반환된 결과값 append()
        sb.append(result);

        // bw로 출력하기 위해 문자열로 변환 후 write
        bw.write(sb.toString());
        bw.flush();

        // 자원 반납
        bw.close();
        br.close();
    }

    // N! 팩토리얼을 계산할 재귀함수 메서드
    // return 타입이 long인 이유는 20!은 int 타입으로 담을 수 있는 크기의 값이 아니다.
    public static long factorial(int n) {
        // 만약 입력값이 1보다 작다면 1을 return
        if (n <= 1) {
            return 1;
        }
        // n * (자기자신의 메서드를 호출한다 (n-1)).
        return n * factorial(n - 1);
    }
}

문제 해석

드디어 재귀함수 Chapter까지 단계가 올라왔다. 재귀함수는 싫어하는 이유가 3차원적으로 생각하고 로직을 구성해야해서 항상 이 부분이 싫은건데 이번 문제는 그래도 간단하게 구현할 수 있는 문제라서 다행이라고 생각했다.

factorial의 재귀함수 실행순서는 어떻게 되는가 ?

메서드의 재귀함수 호출의 순서는 다음과 같다. 만약 10!의 값을 게산한다면 다음과같은 과정을 거쳐서 결과값을 도출하게 된다. return 문에서 계속해서 자기자신의 메서드를 (n -1)을 한 값으로 호출하게 되는데 n이 1이 되는 시점에서 모든 메서드의 return문이 실행되면서 계산이 마무리 된다.

// 각 단계에서 메서드가 종료된게 아님, 
// return 문에서 새로운 factorial을 호출할때마다 해당 메서드 결과값 반환을 기다리고 있음
factorial(10) 호출 -> 10 * factorial(9) 
factorial(9) 호출 -> 9 * factorial(8)
factorial(8) 호출 -> 8 * factorial(7)
factorial(7) 호출 -> 7 * factorial(6)
factorial(6) 호출 -> 6 * factorial(5)
factorial(5) 호출 -> 5 * factorial(4)
factorial(4) 호출 -> 4 * factorial(3)
factorial(3) 호출 -> 3 * factorial(2)
factorial(2) 호출 -> 2 * factorial(1)
factorial(1) 호출 -> 종료 조건에 의해 1 반환

// 각 단계에서 값을 반환하고 차례대로 계산 진행
최종적으로 factorial(10)이 3628800을 반환

재귀 함수로 풀지않아도 풀 수 있는 문제이기는 하다.

팩토리얼 문제처럼 while문을 통해서도 충분히 풀 수 있다, 아니면 아래처럼 배열로도 충분히 풀 수 있는 문제이기는 하다. 하기 코드는 팩토리얼의 특성을 이용해서 푼 코드인데, factorial(2) = 2 * factorial(1), factorial(3) = 3 * factorial(2), factorial(4) = 4 * factorial(3), factorial(5) = 5 * factorial(4)… 위와같은 과정을 배열로 구현한 것이다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        // 입력을 위한 BufferedReader 객체 생성
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 0 부터 20까지 인덱스가 필요하기에 21개로 배열설정
        long[] array = new long[21];
        // 팩토리얼은 0과 1은 1값임
        array[0] = array[1] = 1;
        // 팩토리얼의 특징을 이용해서 배열 인덱스마다 팩토리얼 결과값을 할당
        for (int i = 2; i < 21; i++) array[i] = i * array[i - 1];

        // 결과값 출력
        System.out.println(array[Integer.parseInt(br.readLine())]);
        // 자원 반납
        br.close();
    }
}

마무리

재귀함수 Chapter 이지만 재귀험수로 풀고싶지가 않다. 그냥 디버깅도 쉽고 직관적으로 반복문으로 풀면 안되나. 다음에 푸는 재귀함수 문제에서는 재귀함수를 꼭 써야지만 얻을 수 있는 메리트가 있는지 확인해 보고싶다. 이번 문제에서는 속도차이도 없고 더 나은점을 모르겠다.