[프로그래머스] LV.0 구슬을 나누는 경우의 수 - 자바 [78/100]

💬 문제 설명

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

 

🚫 제한 사항

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

 

📢 입출력 예

 

👨‍🏫 입출력 예 설명

 

📃 제출 코드

import java.math.BigInteger;
class Solution {
    public int solution(int balls, int share) {
        int answer = combination(balls, share);
        return answer;
    }
    
    public int combination(int balls, int share) {
        return factorial(balls)
            .divide(factorial(balls - share).multiply(factorial(share))).intValue();
    }
    
    public BigInteger factorial(int n) {
        if (n == 0 || n == 1) return BigInteger.ONE;
        return BigInteger.valueOf(n).multiply(factorial(n - 1));
    }
}

 

✏ 해결방법 & 배운점

문제에 나와있는 힌트를 이용하여 문제를 해결하였습니다.

 

문제에 주어진 공식을 이용하여 `factorial` 메서드를 `long` 타입으로 선언하여 코드를 작성하였지만
테스트 케이스에서 오류가 발생하여 반환타입을 `BigInteger`로 바꾸니 해결할 수 있었습니다.

`BigInteger` 정리

• int와 long 데이터 타입의 크기를 초과하는 숫자를 다루어야 할 때 유용합니다. 
• BigInteger 클래스는 불변(immutable)이며, 수학적 연산을 수행할 수 있는 다양한 메서드를 제공한다.

객체 생성
문자열 또는 다른 숫자 타입으로 초기화할 수 있습니다.

BigInteger bigInt1 = new BigInteger("123456789012345678901234567890");
BigInteger bigInt2 = BigInteger.valueOf(1234567890L);

 

기본 연산
덧셈, 뺄셈, 곱셈, 나눗셈 등의 연산 메서드를 제공합니다.

BigInteger sum = bigInt1.add(bigInt2);        // 덧셈
BigInteger diff = bigInt1.subtract(bigInt2);  // 뺄셈
BigInteger product = bigInt1.multiply(bigInt2); // 곱셈
BigInteger quotient = bigInt1.divide(bigInt2); // 나눗셈
BigInteger remainder = bigInt1.remainder(bigInt2); // 나머지

 

비교 연산

비교 연산을 위해 compareTo 메서드를 제공합니다.

int comparison = bigInt1.compareTo(bigInt2);
if (comparison > 0) {
    System.out.println("bigInt1 is greater than bigInt2");
} else if (comparison < 0) {
    System.out.println("bigInt1 is less than bigInt2");
} else {
    System.out.println("bigInt1 is equal to bigInt2");
}

 

기타 연산
거듭제곱, 최대공약수(GCD), 소수 판별 등의 연산도 가능합니다.

BigInteger power = bigInt1.pow(2); // 제곱
BigInteger gcd = bigInt1.gcd(bigInt2); // 최대공약수
boolean isPrime = bigInt1.isProbablePrime(1); // 소수 판별

BigInteger를 사용한 조합 계산 예제

import java.math.BigInteger;

class Solution {
    public BigInteger solution(int balls, int share) {
        share = Math.min(balls - share, share);

        if (share == 0) {
            return BigInteger.ONE;
        }

        BigInteger answer = solution(balls - 1, share - 1);
        answer = answer.multiply(BigInteger.valueOf(balls));
        answer = answer.divide(BigInteger.valueOf(share));

        return answer;
    }
}

 

• 최소값 선택:
  • share = Math.min(balls - share, share);
  • 조합의 대칭성을 이용하여 share 값을 balls - share와 share 중 더 작은 값으로 설정합니다. 이는 계산량을 줄이기 위한 최적화입니다.
• 기저 사례(Base Case):
  • if (share == 0) { return BigInteger.ONE; }
  • 선택할 개수가 0이면, 경우의 수는 항상 1이므로 BigInteger.ONE을 반환합니다.
• 재귀적 계산:
  • BigInteger answer = solution(balls - 1, share - 1);
  • 하나의 공을 선택했을 때의 경우의 수를 계산하기 위해 재귀적으로 호출합니다.
  • answer = answer.multiply(BigInteger.valueOf(balls));
  • 현재 balls 값을 곱해주어 선택한 경우의 수를 계산합니다.
  • answer = answer.divide(BigInteger.valueOf(share));
  • 중복된 계산을 피하기 위해 share로 나누어 최종 경우의 수를 계산합니다.
• 결과 반환:
  • 최종적으로 계산된 조합 값을 반환합니다.