문제설명
머쓱이는 구슬을 친구들에게 나누어주려고 합니다. 구슬은 모두 다르게 생겼습니다. 머쓱이가 갖고 있는 구슬의 개수 balls와 친구들에게 나누어 줄 구슬 개수 share이 매개변수로 주어질 때, balls개의 구슬 중 share개의 구슬을 고르는 가능한 모든 경우의 수를 return 하는 solution 함수를 완성해주세요.
제한사항
- 1 ≤ balls ≤ 30
- 1 ≤ share ≤ 30
- 구슬을 고르는 순서는 고려하지 않습니다.
- share ≤ balls
입출력 예
| my_string | result | |
|---|---|---|
| 3 | 2 | 3 |
| 5 | 3 | 10 |
입출력 예 설명
입출력 예 #1
- 서로 다른 구슬 3개 중 2개를 고르는 경우의 수는 3입니다.
입출력 예 #2
- 서로 다른 구슬 5개 중 3개를 고르는 경우의 수는 10입니다.
Hint
서로 다른 n개 중 m개를 뽑는 경우의 수 공식은 다음과 같습니다.
풀이
팩토리얼 함수로 문제를 해결하려고 했으나...class Solution {
public int factorial(int num) {
if (num <= 1) {
return num;
} else {
return num * factorial(num - 1);
}
}
public int solution(int balls, int share) {
return factorial(balls)/(factorial(balls-share)*factorial(share));
}
} 결과는 런타임 애러와 실패경우의 수로 오답
원인은 balls과 share수가 같을 때와 factorial()의 최대 값을 고려 하지 않았음.
조건의 최대값이 30!은 2.6525285981219105863630848e+32이다.
long의 범위조차 벗어난다.
그래서....
BigInteger를 사용하여 풀이 했다.
BigInteger의 범위는 무한대이다.import java.math.BigInteger;
class Solution {
public BigInteger factorial(int num) {
if (num <= 1) {
return BigInteger.valueOf(num);
}else{
return BigInteger.valueOf(num).multiply(factorial(num - 1));
}
}
public BigInteger solution(int balls, int share) {
return balls==share ? BigInteger.ONE : factorial(balls).divide((factorial(balls - share).multiply(factorial(share)))) ;
}
}채점에는 통과했으나, 속도가 느리고, 풀이 방법중에서는 가장 주먹구구식 풀이 인것같다.참고
