[JS] 구슬을 나누는 경우의 수

프로그래머스 >  코딩테스트 입문 > 구슬을 나누는 경우의 수

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

문제 설명

머쓱이는 구슬을 친구들에게 나누어주려고 합니다. 구슬은 모두 다르게 생겼습니다. 머쓱이가 갖고 있는 구슬의 개수 balls와 친구들에게 나누어 줄 구슬 개수 share이 매개변수로 주어질 때, balls개의 구슬 중 share개의 구슬을 고르는 가능한 모든 경우의 수를 return 하는 solution 함수를 완성해주세요.

 

제한사항

• 1 ≤ balls ≤ 30
• 1 ≤ share ≤ 30
• 구슬을 고르는 순서는 고려하지 않습니다.
• share ≤ balls

입출력 예 

balls	share	result
3	2	3
5	3	10

Hint

• 서로 다른 n개 중 m개를 뽑는 경우의 수 공식은 다음과 같습니다.

---

처음에 문제에 계산식을 못보고 경우의 수 조합 관련 내용을 찾아보고 계산해보다가 힌트를 보고도 약분해서 계산해보겠다고 씨름하다가 잘 안되서 일단 저 계산식대로라도 풀어보자라고 생각하고 풀었다.

 

const getFactorial = (cur) => (cur > 1 ? cur * getFactorial(cur - 1) : 1);

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

코드 실행으로 간단한 케이스 2개에 해당하는 것은 통과했지만 채점을 해보면 35개의 테스트 중 7개가 실패한다.

 

숫자가 너무 커서 그런가 싶어서 분모가 더이상 커지지 않도록 계산식을 살짝 바꿔보았다.

const getFactorial = (cur) => (cur > 1 ? cur * getFactorial(cur - 1) : 1);

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

 

 

이러면 35개의 테스트 중에 6개가 실패한다..

---

 

BigInt를 사용해보려고 Factorial 반환하는데 BigInt 처음 써봐서 대충 아무렇게나 해보았다.

const getFactorial = (cur) => cur > 1 ? (BigInt(cur) * getFactorial(cur - 1)) : 1;

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

요상한 에러가 날 사로잡는다.. 

재귀함수랑은 못 쓰는 건가 싶어서( => 사실이 아닙니다) 다시 약분을 하기로 한다.

 

function solution(balls, share) {
  return getDenom(balls, balls - share) / BigInt(getFactorial(balls - share));
}

const getFactorial = (cur) => (cur > 1 ? cur * getFactorial(cur - 1) : 1);

const getDenom = (number, length) => {
  let result = 1;
  for (let i = 0; i < length; i++) {
    result *= number - i;
  }
  return BigInt(result);
};

밑에 m! / n! 은 n ~ m 사이의 수만 곱하면 되니까  m - n 의 개수만큼 m에서 -1 씩 해서 n + 1까지 곱하도록 계산했다.

그리고 (m-n)!은 유지.

 

결과는 35개중 34개 성공.. (짜증나 죽는줄 알았다) 

 

---

 

그래서 결국 재귀함수를 포기하고 BigInt끼리 계산해서 결과가 나오도록 해서 성공했다.

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

const getFactorial = (cur) => {
    let result = 1;
    for(let i = 1; i <= cur; i++){
        result = BigInt(i) * BigInt(result);
    }
    return BigInt(result);
}

이제와서 다시 해보니 

const getFactorial = (cur) => cur > 1 ? BigInt(cur) * getFactorial(cur - 1) : BigInt(1);

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

BigInt끼리 곱할 수 있게 재귀함수를 만들어주면 성공하는 것이었다.😥

 

BigInt.. 어렵다

이번주 스터디 주제를 BigInt로 잡아야겠다.