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

https://school.programmers.co.kr/learn/courses/30/lessons/120840

프로그래머스

문제

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

 

풀이

문제 자체는 매우 간단하다.

고등학교 확통에서 배우는 조합을 계산하는 문제이다.

하지만, 숫자의 범위가 매우 커서(1 <= balls <= 30, 1 <= share <= 30) 해결하는 데 어려움이 있었다.

 

필자는 분모와 분자를 따로 계산하여 답을 구하려고 했는데, 분자의 범위가 long을 초과하여 틀렸다.

고민을 좀 하다가, 분모와 분자를 계산하면서 약분하는 방식으로 답을 구했다.

---

🔔 시행착오 과정은 더보기 란에 작성하였습니다.

1. 모든 자료형을 int로 설정하고, 분자(answer)와 분모(div)를 따로 구한 코드 >> 당연히 틀렸다.

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

 

2. 위 코드에서 int를 초과한다는 것을 깨닫고 모든 자료형을 long으로 바꿔보았다. >> 몇 개 더 맞추었지만, 모든 테스트 케이스를 맞추진 못했다.

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

 

3. 조합에서 5C2와 5C3이 같다는 것을 이용하여 최대한 곱셈을 적게 하도록 반복문의 범위를 변경하였다. >> 역시 모든 케이스를 맞추진 못했다. (반례 : 30C15를 구하기 위해 30부터 16까지 곱하면 long 범위보다 훨씬 커진다.)

class Solution {
    public long solution(int balls, int share) {
        long answer = 1;
        
        for(long i = balls; i > Math.max(balls - share, share); i--) {
            answer *= i;
        }
        
        long div = 1;
        for(long i = 1; i <= Math.min(balls - share, share); i++) {
            div *= i;
        }
        
        return answer / div;
    }
}

 

4. 3번 코드의 반복문을 합쳤다. 그러면서 분자에서 분모를 계속 나누는 과정을 수행하였더니 모든 테스트 케이스를 맞출 수 있었다.

class Solution {
    public long solution(int balls, int share) {
        long answer = 1;
        
        long div = 1;
        for(int i = balls; i > Math.max(balls - share, share); i--) {
            answer *= i;
            div *= balls - i + 1;
            if(answer % div == 0) {
                answer /= div;
                div = 1;
            }
        }
        
        
        return answer / div;
    }
}

---

코드

class Solution {
    public long solution(int balls, int share) {
        long answer = 1;
        
        long div = 1;
        for(int i = balls; i > Math.max(balls - share, share); i--) {
            answer *= i;
            div *= balls - i + 1;
            if(answer % div == 0) {
                answer /= div;
                div = 1;
            }
        }
        
        
        return answer / div;
    }
}

 

틀린 부분이 있다면 정정해 주시면 감사하겠습니다.
궁금한 부분이 있거나, 다른 아이디어가 있으시면 자유롭게 댓글 남겨주세요!