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

프로그래머스 - level 0 구슬을 나누는 경우의 수

주어진 테스트 케이스는 다 맞았는데 또다시... 34.3% 맞았다. 심지어 3개는 런타임 에러 났음 ㅋㅋㅋㅋ...

팩토리얼을 구현하는 재귀는 일단 보류

class Solution {
    public int solution(int balls, int share) {
        int answer = fac(balls) / (fac(balls-share) * fac(share));
        return answer;
    }
    int fac(int num) {
        if(num==1)
            return 1;
        return fac(num-1)*num;
    }
}

 

연산 개수를 줄여보았다.

이번에는 런타임 에러는 안 났는데 정답률은 48.6%...

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

 

정수 범위를 넘어서 그런 거였다. ㅎ... BigInteger 사용해서 해결.

import java.math.BigInteger;

class Solution {
    public int solution(int balls, int share) {
        BigInteger answer = new BigInteger("1");
        for(int i=balls; i>(balls-share); i--) {
            answer = answer.multiply(BigInteger.valueOf(i));
        }
        for(int i=2; i<=share; i++) {
            answer = answer.divide(BigInteger.valueOf(i));
        }
        return answer.intValue();
    }
}

 

타인의 풀이 중 멋진 풀이가 있어서 가져와봤다... 조합의 성질을 이용한 재귀

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;
    }
}

balls부터 balls-share+1까지 순서대로 곱하면서 동시에

share부터 1까지 순서대로 나누는 방식

for문으로도 만들 수 있을 것 같긴한데, 재귀를 잘 활용한 것 같음.