[프로그래머스] 구슬을 나누는 경우의 수

코드 힌트

두 가지 방법을 사용할 수 있습니다:

1. BigInteger 사용하기
   • BigInteger 클래스는 매우 큰 숫자를 안전하게 처리할 수 있습니다. 예를 들어, 30! (30의 팩토리얼)을 계산할 때, int 또는 long의 범위를 초과할 수 있습니다. BigInteger는 이러한 경우에도 안전하게 숫자를 관리할 수 있는 클래스입니다.
   • 제한 사항에 따라 balls와 share가 30까지 갈 수 있으므로, 팩토리얼 계산 시 BigInteger를 사용하여 계산할 수 있습니다.
   • 단점으로는 조작을 하기 힘들다는 단점이 있습니다.
2. BigInteger 없이 풀기
   • 이 문제는 조합 공식을 사용해 풀 수 있습니다. 조합 공식은 n! / ((n-m)! * m!)입니다. 이를 두 단계로 나누어 풀 수 있습니다.
   • 첫 번째 단계는 n! / m!을 먼저 계산하는 것입니다. 이는 m+1 * m+2 * ... * n과 같습니다.
   • 두 번째 단계는 (n-m)!로 나누는 것입니다. 이 부분은 간단히 순차적으로 계산하여 나누는 방식으로 최적화할 수 있습니다.
   • 이 방법은 메모리와 계산 속도를 최적화할 수 있으며, BigInteger를 사용하지 않고도 문제를 해결할 수 있습니다.

 

저는 BigInteger로 풀지 않았습니다. 혹시 BigInteger로 푸시고 싶은 분은 다른 사람 코드를 참고하시면 될 것 같습니다.

 

---

정답은 더보기 클릭

class Solution {
    public int solution(int balls, int share) {
        double result = 1;
        
        // 조합 공식을 사용해 (balls! / share!) 부분을 계산합니다.
        // (share+1) * (share+2) * ... * (balls)
        for (int i = share + 1; i <= balls; i++) {
            result *= i;
        }
        
        // 나누기 부분 (balls-share)!를 계산합니다.
        // 여기서는 간단히 for 루프를 통해 순차적으로 나누는 방식으로 최적화합니다.
        for (int i = 2; i <= balls - share; i++) {
            result /= i;
        }
        
        // 결과를 반올림하여 int로 변환하여 반환합니다.
        return (int)Math.round(result);
    }
}