구슬을 나누는 경우의 수(with.Java)

“구슬을 나누는 경우의 수” 문제에 대하여 알아본 글입니다.

코딩 테스트 문제를 풀며, 풀었던 문제에 대한 회고와 다른 풀이 방법을 알아보며, 알아가고자 합니다.

문제에 대해 먼저 알아보겠습니다.

문제

머쓱이는 구슬을 친구들에게 나누어주려고 합니다.

구슬은 모두 다르게 생겼습니다.

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

제한사항

1 ≤ balls ≤ 30

1 ≤ share ≤ 30

구슬을 고르는 순서는 고려하지 않습니다.

share ≤ balls

입출력 예시

문제에 대한 나의 풀이

class Solution {
    public int solution(int balls, int share) {
        double answer = 1;

        for(int i = 0; i < share; i++){
            answer = answer * (balls - i) / (i+1);
        }

        return (int)answer;
    }
}

풀이 설명

이항 계수를 구하기 위해 팩토리얼 계산을 사용하여 효율적으로 경우의 수를 계산하고 있습니다.

결과를 double에서 int로 형변환하여 반환하고 있습니다. 숫자가 매우 커질 경우, answer에 1을 초기화하고 이를 계속해서 누적하면서 정수의 범위를 초과할 수 있습니다.

double로 형변환하고 나중에 다시 int로 변환하는 것은 부정확할 수 있습니다.

큰 숫자에 대한 계산은 정수 오버플로우의 가능성이 있습니다.

따라서 더 큰 숫자에 대한 계산을 위해 long 또는 BigInteger를 고려할 수 있습니다.

개선 가능한 점

형변환 주의: 정수 계산의 정확성을 위해 answer를 계산할 때 double로 유지하고 필요한 경우 형변환을 고려합니다.

수학적 최적화: 경우의 수를 계산하는 부분에서 수학적 최적화를 고려하여 효율성을 높일 수 있습니다.

정수 오버플로우 방지: 큰 숫자에 대한 경우의 수를 계산할 때 오버플로우를 방지하기 위해 long 또는 BigInteger를 사용합니다.