[Programmers] 구슬을 나누는 경우의 수 (팩토리얼 / 재귀함수X)

 

 

 

 

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

팩토리얼 -> 재귀함수로 푸는 문제라 생각하고 아 문제 잘풀었다 하고 제출했는데 와다다 실패

-> 재귀 범위 넘어감

40 몇점

 

 

class Solution {
    public long solution(int balls, int share) {
        return factorial(balls) / (factorial(balls - share) * factorial(share));
    }
    
    private long factorial(int num) {
        long fac = 1; 
        for(int i=1; i<=num; i++) {
            fac *= i;
        }
        return fac;
    }
}

재귀함수 없이 팩토리얼 구현 + long 변수에 담기 

60 몇점

 

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

아예 약분해서 풀기 

-> 오버플로우 발생할 수 있음 + long 넘어갈 수 있음

88점

 

 

class Solution {
    public int solution(int balls, int share) {
        
        long ans = 1;
        int rest = 1;
        
        for(int i = share + 1; i <= balls; i++) {
            ans *= i;
            ans /= rest;
            rest ++;
        }
        
        return (int)ans;
    }
}

곱셈과 나눗셈 반복 -> 크기 작아짐

통과 ㅠ