프로그래머스 Lv.0 | 구슬을 나누는 경우의 수

문제

https://school.programmers.co.kr/learn/courses/30/lessons/120840

 

 

💻 풀이

원래 5, 6, 7, 28, 33, 34, 35번 테스트 케이스에서 에러가 났다.

원인을 찾아보니까 balls와 share가 최대 30인데 곱셈을 축적해서 팩토리얼을 구하는 방식으로는 값을 감당하지 못해서 그런거였다. 분수 부분 결과값이 너무 커서 그런가 생각해서 factorial(balls) / factorial(balls - share) / factorial(share)로 이 부분을 바꿔봤는데도 틀린다. 내 생각에는 여전히 수가 크기때문에 계속 부동소수점 이슈가 발생하는 듯 싶다. 그래서 그냥 BigInt()를 씌워서 아래와 같이 풀었다.

function solution(balls, share) {
    return factorial(balls) / (factorial(balls - share) * factorial(share));
}

function factorial(n) {
    return Array.from({length: n}, (v, i) => i + 1).reduce((acc, curr) => acc *= BigInt(curr), BigInt(1));
}

 

약간 더 개선한 버전 - n개 중 m개를 선택할 때 m = 0, m === n인 경우 결과값이 1이라는 것을 이용해 약간 최적화할 수 있다.

function solution(balls, share) {
    if(share === 0 || balls === share) return 1;
    return factorial(balls) / (factorial(balls - share) * factorial(share));
}

function factorial(n) {
    return Array.from({length: n}, (v, i) => i + 1).reduce((acc, curr) => acc *= BigInt(curr), BigInt(1));
}