[Java] Programmers - 구슬을 나누는 경우의 수

Jae Chan·2023년 1월 6일

Java 코딩 테스트 프로그래머스

Coding-Test

목록 보기

3/10

※ 프로그래머스 코딩테스트 연습 문제 중 하나 입니다.

구슬을 나누는 경우의 수 ❔

문제 설명 💡

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

제한 사항 ❗

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

입출력 예

balls	share	result
3	2	3
5	3	10

입출력 예 설명

입출력 예 #1

서로 다른 구슬 3개 중 2개를 고르는 경우의 수는 3입니다.

입출력 예 #2

서로 다른 구슬 5개중 3개를 고르는 경우의 수는 10입니다.

해석 🔑

package Programmers_Lv0;
/*
 *  Lv.0 : 구슬을 나누는 경우의 수
 *  Site : https://school.programmers.co.kr/learn/courses/30/lessons/120840
 */
public class Lv0_BallsFactorial {
    public int solution(int balls, int share) {
        int answer = facto(balls) / ((facto(balls - share)) * facto(share));
        
        return answer;
    }  

    public int facto(int n) {
        if(n <= 1)
            return n;
        else
            return n * facto(n - 1);
    }
}

이 문제는 힌트로 나와있던 공식이 도움됐다. 재귀함수를 이용해 팩토리얼 메소드를 생성 후 경우의 수 공식 값을 반환하도록 작성했다.

여기서 문제 발생. 🤦‍♂️
테스트는 원활하게 통과했으나 제출 후 채점하는 과정에서 통과하지 못했다.

이 코드의 경우엔 재귀함수를 사용하다보니 변수를 담는 데이터 크기가 부족했기 때문에 자료형의 크기가 커야했다.

처음에는 long 자료형을 사용해봤는데 여전히 똑같았다.
해결하기 위해 long 보다 큰 BigInteger 라는 클래스를 이용했음 !

문제 해결 ✔️

/*
 *  코딩 테스트 연습 문제 : 구슬을 나누는 경우의 수
 *  Site : https://school.programmers.co.kr/learn/courses/30/lessons/120840
 */
package Programmers_Lv0;
import java.math.BigInteger;

 public class Lv0_BallsFactorial {
    public BigInteger solution(int balls, int share) {
        /*  경우의 수 연산 
         *  balls! / (balls - share)! * share!
         *  여기서 '!'는 팩토리얼을 의미한다.
         */
        BigInteger answer = facto(balls);
        BigInteger downNum0 = facto(balls - share).multiply(facto(share));
        return answer.divide(downNum0);
    }  

    public BigInteger facto(int n) {
        BigInteger factoNum = BigInteger.ONE;
    
        for(int i = 1; i <= n; i++) {
            factoNum = factoNum.multiply(new BigInteger(Integer.toString(i)));
        }

        return factoNum;
    }
}