[Java] 백준(브론즈-5) 10872번 - 팩토리얼

문제 풀이

---

이 문제는 재귀 알고리즘으로 접근해야 한다.

재귀란?
자신을 정의할 때 자기 자신을 다시 참조하는 방식을 재귀라고 한다.

재귀를 구현하며 유의할 점

1. 재귀가 반복적으로 호출되면 자바에서는 Stack OverFlow 에러가 발생하게 된다. 재귀함수는 반복적으로 호출하는 만큼 메모리를 차지하기 때문에 매우 느리기 때문에 재귀함수는 평상시 자주 쓰이지는 않는다.
2. 재귀 함수의 종료 조건은 명확해야 한다. 무한 루프에 빠지지 않도록 종료조건을 자세히 작성해야 한다.

재귀함수를 이용하면서 고려해야 할 부분을 항상 주의하며 구현하자.
또한 재귀함수는 대부분 반복문으로 대체가 가능하기 때문에 반복문으로도 구현할 수 있음을 명심하자.

재귀함수 활용하기

먼저 재귀함수를 이용해 문제를 풀어보자.
주어진 N을 1씩 빼가며 곱하면서 N이 1이 되었을 때 곱했던 결과값을 반환하면 된다.

예를 들어보면 다음과 같다.

N = 10, 재귀함수(9)
N = 9, 재귀함수(8)
N = 8, 재귀함수(7)
N = 7, 재귀함수(6)
N = 6, 재귀함수(5)
N = 5, 재귀함수(4)
N = 4, 재귀함수(3)
N = 3, 재귀함수(2)
N = 2, 재귀함수(1)
N = 1 -> 재귀함수 종료

그렇다면 코드로 작성해보자.

public static int factorial(int n) {
    if(n <= 1) return 1;
    return n * factorial(n-1);
}

0!는 1이기 때문에 N이 0이거나 1일 때는 1을 반환한다.
1이 아니라면 N * factorial(N-1) 로 N을 1씩 빼가며 곱한 값을 반환하면 된다.

결과값 범위
문제의 요구사항를 보면 N의 범위는 0~12인데, 13! 부터는 6227020800으로 int형의 범위를 벗어난다.
N의 범위가 13을 넘는다면 꼭 long형으로 풀자.

반복문 활용하기

재귀를 사용하지 않고 반복문으로도 문제를 풀 수 있다.
반복문으로 재귀를 구현하면 재귀 방식보다 메모리를 덜 차지하기에 유리하다.
재귀의 깊이가 깊어질수록 메모리 초과가 발생할 가능성이 높기에 반복문으로 재귀를 풀 수 있다면 좋을 것 같다.

재귀방식과 동일하게 반복문도 N이 1이 될 때까지 N을 곱해가며 결과값을 반환하면 된다.
코드를 작성해보자.

int res = 1;
while(N != 1) {
    res *= N;
    N--;
}

곱한 값을 저장해나갈 res 변수를 선언해주고, while문을 돌며 N이 1이 될 때까지 res에 N을 1씩 빼가며 곱해주면 된다.

작성코드

작성코드 - 재귀함수 활용

import java.io.*;

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(N)+"\n");
        
        bw.flush();
        bw.close();
        br.close();
    }

    public static int factorial(int n) {
        if(n <= 1) return 1;
        return n * factorial(n-1);
    }
}

작성코드 - 반복문 활용

import java.io.*;

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());
        int res = 1;
        while(N != 1) {
            res *= N;
            N--;
        }
        bw.write(res+"\n");
        
        bw.flush();
        bw.close();
        br.close();
    }
}

회고

• 본격적으로 재귀함수 카테고리 문제를 풀기 시작했는데, 재귀를 반복문으로 대체하여 구현할 줄 알아야 함을 느꼈다.