[프로그래머스] 구슬을 나누는 경우의 수

문제를 보자마자 팩토리얼 재귀함수로 구하면 된다고 생각했었다.

class Solution {
        public int solution(int balls, int share) {
            if (balls == share) return 1;
            return makeFactory(balls) / (makeFactory(balls - share) * makeFactory(share));
        }

        public int makeFactory(int num) {
            if (num == 0) {
                return 1;
            }

            return num * makeFactory(num - 1);
        }
    }
}

- 그런데 이렇게 하니까 안되는 경우가 있었음

- 인터넷 찾아보니 int 범위를 넘는 케이스가 존재하기 때문에 어쩔 수가 없음

- 4바이트의 메모리가 할당되며 아래 영역 넘어버림

-2,147,483,648 ~ 2,147,483,647

 

import java.lang.*;
import java.math.*;

class Solution {
    public BigInteger solution(int balls, int share) {
        if(balls == share) return BigInteger.ONE;
        BigInteger answer;

        BigInteger bunja = BigInteger.ONE;

        for (int i = balls ; i > balls-share ; i--){
            bunja = bunja.multiply(BigInteger.valueOf(i));
        }

        BigInteger bunmo = BigInteger.valueOf(factorial(share));

        answer = bunja.divide(bunmo);


        return answer;
    }

    public static long factorial( int num){
        if (num == 1 || num == 0) return 1;

        return num * factorial(num-1);
    }


}

- BigInteger는 java.math에 있으며 Wrapper 클래스의 일종임