[프로그래머스 코딩테스트] 구슬을 나누는 경우의 수(Java)

  문제 설명

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

 

  제한사항

• 1 <= balls <= 30
• 1 <= share <= 30
• 구슬을 고르는 순서는 고려하지 않습니다.
• share <= balls

 

  입출력 예

balls	share	result
3	2	3
5	3	10

import java.math.BigInteger;
class Solution {
    public int solution(int balls, int share) {
        BigInteger top = BigInteger.ONE;
        BigInteger bot = BigInteger.ONE;
        for (int i = balls; i >= balls - share + 1; i--) {
            top = top.multiply(BigInteger.valueOf(i));
        }
        for (int i = 1; i <= share; i++) {
            bot = bot.multiply(BigInteger.valueOf(i));
        }
        BigInteger result = top.divide(bot);
        int answer = result.intValue();
        return answer;
    }
}

  BigIntger 타입의 변수 top과 bot을 생성하고 1로 초기화합니다.

  for문이 balls부터 balls - share + 1만큼 순회하면서 multiply 메소드를 이용하여 top에 i를 곱하기 할당합니다.

  for문이 share까지 순회하면서 multiply 메소드를 이용하여 bot에 i를 곱하기 할당합니다.

  BigInteger 타입의 result 변수를 생성하여 top을 bot으로 나눈 값을 담습니다.

  int형 answer에 담기 위해 BigInteger 타입을 intValue 메소드를 이용하여 정수형으로 형변환을 한 뒤 반환합니다.

 

  이 문제는 조합을 이용한 문제로, 순서 없이 서로 다른 n 개 중에서 r 개를 선택하는 경우의 수입니다. 기준이 빡빡하여 재귀 호출로는 풀 수 없었고, long으로도 해결할 수 없는 테스트 케이스가 있었습니다. 이런저런 방법이 있습니다만 개인적으로는 bigInteger를 이용하여 푸는 것이 기본적인 풀이에 부합한다고 생각해서 이렇게 풀었습니다. 수학적인 머리가 된다면 먼저 나눈다든지 하는 기술이 있었을 텐데…….

  세 달째 0단계를 푸는 사람이 있다 충격 공포 실화 ^^...