[프로그래머스 Lv.0] 구슬을 나누는 경우의 수(Java)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/120840#

프로그래머스

풀이

이 문제는 조합(Combination)을 구하는 문제이다. balls개 중에서 share개를 선택하는 경우의 수를 계산하면 된다.

일반적으로 조합은 팩토리얼을 이용해 계산하지만, 팩토리얼은 값이 매우 빠르게 커져 오버플로우가 발생할 수 있다. 따라서 팩토리얼을 직접 계산하지 않고 곱셈과 나눗셈을 반복하며 결과를 구하는 방식을 사용한다.

또한 조합은 nCr = nC(n-r)의 성질을 만족하므로, 반복 횟수를 줄이기 위해 share를 더 작은 값으로 변경한다.

 

share = Math.min(share, balls - share);

 

예를 들어 10C7은 10C3과 같으므로, 3을 선택하는 경우만 계산하면 반복 횟수를 줄일 수 있다.

이후 반복문에서는 분자와 분모를 한 단계씩 계산하여 결과를 갱신한다.

 

answer = answer * (balls - share + i) / i;

 

예를 들어 5C2를 계산하는 경우에는 다음과 같이 진행된다.

• (4 / 1)
• (4 × 5) / 2

최종 결과는 10이 되어 5C2 = 10을 구할 수 있다.

이처럼 중간 계산에서 나눗셈을 함께 수행하면 불필요하게 큰 수가 만들어지는 것을 방지하면서 조합을 효율적으로 계산할 수 있다.

코드

class Solution {
    public long solution(int balls, int share) {
        long answer=1;
        
        share=Math.min(share, balls-share);
        
        for(int i=1;i<=share;i++){
            answer=answer*(balls-share+i)/i;
        }
        
        return answer;
    }
}