구슬을 나누는 경우의 수
문제 설명
머쓱이는 구슬을 친구들에게 나누어주려고 합니다. 구슬은 모두 다르게 생겼습니다. 머쓱이가 갖고 있는 구슬의 개수
balls와 친구들에게 나누어 줄 구슬 개수share이 매개변수로 주어질 때,balls개의 구슬 중share개의 구슬을 고르는 가능한 모든 경우의 수를 return 하는 solution 함수를 완성해주세요.
제한사항
- 1 ≤ balls ≤ 30
- 1 ≤ share ≤ 30
- 구슬을 고르는 순서는 고려하지 않습니다.
- share ≤ balls
Hint
- 서로 다른 n개 중 m개를 뽑는 경우의 수 공식은 다음과 같습니다.
사고 과정
- Hint를 통해 팩토리얼이 필요한 것을 알았고, 재귀와 dp중 dp를 이용해서 풀어보도록 함
- dp에서 사용할 점화식을 구현(팩토리얼 메모이제이션용)
=> dp[i] = dp[i - 1] * i - 저장된 dp 배열을 이용하여 n, n-m, m의 값에 해당하는 인덱스를 참조하여 식에 대입 후 결과값 출력
첫번째 코드
function solution(balls, share) {
var answer = 0;
let dp = [];
dp[0] = 1;
for(let i = 1; i <= 30; i++)
dp[i] = dp[i-1] * i;
return dp[balls] / (dp[balls - share] * dp[share]);
}결과
테스트케이스 5, 6, 7, 28, 33, 34, 35번 실패
첫번째 코드의 문제점
첫번째 코드에서는 JavaScript의 숫자형의 최대값과 소수점 최대 자릿수를 전혀 상정하지 않고, 오버플로우를 비고려한 코드로 작성했습니다.
30!의 값은 265252859812191058636308480000000인데, 제가 기억하는 숫자형의 최대값은 Number.MAX_SAFE_INTEGER = 9007199254740991의 값으로 30!의 값을 일반적인 방법으로는 절대 받을 수 없다고 판단했습니다.
1차 코드 해결 방안
숫자형의 최대값으로 처리가 안된다면, 큰 수를 저장하고 사용할 수 있는 BigInt()를 써서 풀이해보기로 했습니다.
2차 코드(성공)
function solution(balls, share) {
var answer = 0;
let dp = [];
dp[0] = BigInt(1);
for(let i = 1; i <= 30; i++)
dp[i] = dp[i-1] * BigInt(i);
return dp[balls] / (dp[balls - share] * dp[share]);
}JavaScript의 정수형 최대값은 9007199254740991이 아니다?
최대값 정보를 찾아보던 중에 Mdn에서 Number.MAX_VALUE 라는 값을 보게 되었습니다.
실제 JavaScript의 최대값은 이 값이였으며 이 수치는 무려 1.7976931348623157e+308 이였습니다.
그렇다면 문제는 최대값이 아니라 제 코드 자체에 무슨 문제가 있다는 결론이 나오는데, 가장 미심쩍은 부분은 나누기였습니다. 생각해보니 나누기를 하게 되면 JavaScript는 암묵적 정수 형변환이 되지 않고, 실수로 나타나게 된다는 점을 간과하여 이런 결과가 나타났습니다.
따라서 마지막 반환값을 정수로 바꿔서 보내주면 되기 때문에 첫 번째 코드의 return에서 Math.round를 이용하여 정수화하게 되면, 정상적으로 정답이 됩니다.
최종 코드
function solution(balls, share) {
var answer = 0;
let dp = [];
dp[0] = 1;
for(let i = 1; i <= 30; i++)
dp[i] = dp[i-1] * i;
return Math.round(dp[balls] / (dp[balls - share] * dp[share]));
}풀이 후기
JavaScript의 최대, 최소 값을 정확히 알고 문제를 접근했다면 BigInt를 생각하지 않고 정수화를 생각했을텐데 너무 당황했습니다.
이와 별개로 재귀함수로 풀이를 해도 쉽게 문제가 풀리는 것을 확인했고, 테스트해보니 통과 속도가 재귀함수보다 약 3배나 느렸습니다.(!!)
아무래도 실질적인 계산은 총 세번만 하기 때문에 시작부터 값의 크기에 관계없이 dp 메모이제이션 배열을 만들어놓는 것에서 시간적 소요가 많은 것 같습니다.
