[프로그래머스]구슬을 나누는 경우의 수

구슬을 나누는 경우의 수

문제 설명

머쓱이는 구슬을 친구들에게 나누어주려고 합니다. 구슬은 모두 다르게 생겼습니다. 머쓱이가 갖고 있는 구슬의 개수 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입니다.

---

나의 풀이 코드

import java.math.BigInteger;


class Solution {
    public int solution(int balls, int share) {
        
        BigInteger num1 = BigInteger.ONE;
        BigInteger num2 = BigInteger.ONE;
        BigInteger num3 = BigInteger.ONE;
        
        for (int i = 1; i <= balls; i++) {
            num1 = num1.multiply(BigInteger.valueOf(i));
            if (i <= balls - share) {
                num2 = num2.multiply(BigInteger.valueOf(i));
            }
            if (i <= share) {
                num3 = num3.multiply(BigInteger.valueOf(i));
            }
        }
        
    
        
        
        BigInteger answer = num1.divide(num2.multiply(num3));
        
        return answer.intValue();
    }
}

처음에 재귀함수로 factorial을 만들어보았는데 시간도 500ms 이상 걸리는 케이스도 있고 실패하는 케이스도 있었다. 결국 반복문으로 풀었는데 자꾸 실패가 떠서 찾아본 결과 BigInteger를 사용했더니 정답이었다. 실행시간도 케이스당 1ms 정도였다.

배운점

int와 long의 메모리 크기는 범위가 정해져 있어 그 범위를 넘어가면 0으로 출력된다. 반면 BigInteger는 문자열 형태로 이루어져 있어 숫자의 범위가 무한하기에 어떠한 숫자이든지 담을 수 있다고 한다.

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

        if (share == 0)
            return 1;

        long result = solution(balls - 1, share - 1);
        result *= balls;
        result /= share;

        return result;
    }


}

위에 남이 푼 코드를 보면 long타입을 쓰고 재귀함수를 이용해서 공식을 구현한것 같다.

아무리 재귀함수라도 런타임을 넘지 않도록 잘 짜면 된다.