머쓱이는 구슬을 친구들에게 나누어주려고 합니다. 구슬은 모두 다르게 생겼습니다. 머쓱이가 갖고 있는 구슬의 개수 balls와 친구들에게 나누어 줄 구슬 개수 share이 매개변수로 주어질 때, balls개의 구슬 중 share개의 구슬을 고르는 가능한 모든 경우의 수를 return 하는 solution 함수를 완성해주세요.
제한사항
- 1 ≤
balls≤ 30 - 1 ≤
share≤ 30 - 구슬을 고르는 순서는 고려하지 않습니다.
share≤balls
🤓 나의 풀이
const getFac = (num) => {
let answer = 1;
for (let i=1; i<= num; i++) {
answer *= i;
}
return answer;
}
function solution(balls, share) {
let numer = getFac(balls);
let denom = getFac(balls - share) * getFac(share);
return Math.round(numer / denom);
}하 솔직히 이건... 수학 다 까먹어서 개로웠음.
문제가 감도 안잡혀서 이를 어쩌누... 하던 차에
힌트 발견!
오! 팩토리얼이다! 사실 난 팩토리얼이라는 용어보다 쾅이라는 말이 더 익숙한 사람... (feat. 수학귀신)
암튼 이 공식에 의존해서 풀 수밖에 없었다.
생각을 깊이 하진 못했다. getFac() 함수를 만들어서 팩토리얼 값을 구하도록 했다.
그래서 공식 그대로 분모, 분자에 적용해서 나눠주었다.
그런데?! 일부 케이스에서 실패가 뜨는 게 아니겠음?!
여기까지 했는데... 모르겠어서 이후는 다른 사람들의 답변을 참고했다.
Math.round()함수로 반올림을 해줘야만 통과! 왜...?
이 이유는 잘 모르겠다... 그래서 참고한 블로그와 뤼튼의 답변을 가져와봤다.
그렇다구 한다! 계산 정밀도를 위해 반올림을 해준다고 하니 이후에도 이를 참고하여 답변을 적을 일이 있음 좋겠다.
😲 다른 풀이 1
const 팩토리얼 = (num) => num === 0 ? 1 : num * 팩토리얼(num - 1)
function solution(balls, share) {
return Math.round(팩토리얼(balls) / 팩토리얼(balls - share) / 팩토리얼(share))
}const 팩토리얼이라...
- 재귀함수를 이용하여 주어진 숫자
num의 팩토리얼을 계산한다. 오...0!은 1로 정의되고 재귀적으로 계속 자기 자신을 호출하여 num이 0이 될 때까지 각 숫자를 곱해나가는 것이다. - 이후 solution 함수에서 답을 구한다. balls의 팩토리얼을 계산하고, 그 결과를 ball-share의 팩토리얼과 share의 팩토리얼로 나눈다.
콤비네이션 공식(Combination)
C(n, k) = n! / (k! * (n-k)!)을 구현한 것
- 그리고 마지막으로 Math.round() 함수를 사용하여 계산 결과를 반올림하여 반환한다. 부동 소수점 계산의 정밀도 문제로 인해 발생할 수 있는 극미한 오차를 보정하기 위함
🫡 다른 풀이 2
function solution(balls, share) {
var result = 1;
while(share > 0){
result = result * balls / share;
balls = balls - 1;
share = share - 1;
}
return Math.round(result);
}이 방식은 조합의 공식을 직접 계산하지 않고, 반복문을 사용하여 조합의 결과를 구한다. 각 단계에서 balls에서 1을 빼고 share에서도 1을 빼면서 그 비율을 result에 곱해나간다. 이를 통해 팩토리얼을 계산하지 않고도 조합의 결과를 얻을 수 있다.
근데 사실 잘 이해가 안 가...
반복문을 통해 계산 과정을 단순화하여 큰 숫자에 대한 오버플로우나 정밀도 문제가 발생하지 않는다. 이 방식이 팩토리얼을 직접 계산하는 것보다 더 효율적이고 큰 수에 대해서도 안전하게 조합의 수를 계산할 수 있다고 한다.
