JS 팩토리얼과 BigInt

balls : 구슬의 개수
share : 친구들에게 나누어 줄 구슬 개수
balls개의 구슬 중 share개의 구슬을 고르는 가능한 모든 경우의 수를 return

서로 다른 n개 중 m개를 뽑는 경우의 수 공식
n! / (n-m)! * m!

BigInt의 특징

• 2^53 - 1 보다 더 큰 수를 다룰 수 있음
• 정수 리터럴 끝에 n을 붙이거나
  함수 BigInt를 호출하면 문자열이나 숫자를 가지고 BigInt 타입의 값을 만들 수 있음
• Number 타입과 같이 섞어 연산할 수 없음. 다만 비교는 가능함.
• BigInt는 BigInt 끼리 비교, 연산 (일반 Number보다는 속도 측면에서 느림)
• Math 내장 객체의 메서드도 사용할 수 없음
• +, *, -, **, % 연산자는 사용 가능함.

나의 풀이

function solution(balls, share) {
    function factorial(n) {
        return (n > 1) ? n * factorial(n - 1) : n;
    }

    return factorial(balls)/(factorial(balls-share)*factorial(share));
}

solution(3,2)
solution(5,3)일 경우 정상적으로 작동하지만 숫자가 커지면 실행결과가 일치하지 않음.


이 문제에서 factorial 계산 시 매우 큰 수가 연산될 수 있기에 BigInt를 사용하여 연산해야함.

let max = Number.MAX_SAFE_INTEGER // 9007199254740991
let min = Number.MIN_SAFE_INTEGER //-9007199254740991

console.log(max++) // 9007199254740991
console.log(min--) //-9007199254740991

연산이 정상적으로 이루어지지 않는 것을 볼 수 있음. 최대치 이상의 수를 사용하기 위해선 BigInt를 사용해야하는데 이때 BigInt는 Number와 연산, 비교를 할 수 없으며 검증시엔 Number.isSafeInteger()사용.

console.log(Number.isSafeInteger(max++) // false

BigInt를 사용한 풀이

function solution(balls, share) {
    function factorial(n){
        return (n > 1) ? BigInt(n) * factorial(n - 1) : BigInt(n);
    }
    
    if(balls === share){
       return 1;
      // balls와 share 수가 같을 경우 1가지 경우의 수만 가능하므로
    } else {
        return factorial(balls) / (factorial(balls - share) * factorial(share));
    }
}

참고 블로그
MDN : BigInt