[프로그래머스] 코딩테스트 입문 : 구슬을 나누는 경우의 수

| 문제

머쓱이는 구슬을 친구들에게 나누어주려고 합니다. 구슬은 모두 다르게 생겼습니다.

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

| 제한 사항

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

| 입출력 예

balls	share	result
3	2	3
5	3	10

| 힌트

balls가 3이고 share가 2라면 result는 (3 * (3-1)) / (2 * (2-1))이고

balls가 5이고 share이 3이라면 result는 (5 * (5-1) * (5-2)) / (3 * (3-1) * (3-2))입니다.

다시 말해서 분자에는 share개만큼 balls에서 하나씩 뺀 값을 곱하고

분모에는 share를 1까지 곱한 값 즉, 팩토리얼 값을 곱해서 둘을 나눠주는 문제입니다.

다만, 일부 테스트 데이터가 굉장히 큰 값을 포함하고 있으므로 이를 고려해서 식을 구성하여야 합니다.

| 잘못된 풀이

힌트에서 알려드린 대로 큰 수부터 적은 수로 분자와 분모를 계산한 다음 마지막에 나눴습니다.

정상적인 로직이지만, 5,6,7,29,32,33,34번에서 실패가 발생합니다.

코드를 실행했을 때는 잘 동작하는 데 왜 제출만 하면 이런 일이 생길까요?

public class Solution {
    public int solution_wrong(int balls, int share) {
    	long num = 1;
    	long den = 1;
        for(int i = 0 ; i < share ; i++) {
        	num *= balls-i;
        	den *= share-i;
        }
        return (int)(num/den);
    }
}

자바의 정수형 자료형의 범주에 제약이 있기 때문입니다.

아래 코드를 통해서 30부터 16까지 숫자를 곱해나가 보겠습니다.

숫자가 커지다가 마지막에 -5,769,043,765,476,591,616이 출력되는 것을 확인할 수 있습니다.

자바에서 정수형 자료형이 가지는 값은 9,223,372,036,854,775,807인데 마지막 직전 숫자  745,747,076,954,880,00에 16을 곱하면 해당 범주를 벗어나게 돼요.

long test = 1;
for(int i = 30 ; i >= 16 ; i--){
    System.out.println(test);
    test *= i;
} 

| 풀이 1

구슬을 나누는 경우의 수 문제를 해결하려면

분자의 값이 커지는 것을 방지하기 위해서 분모로 나눠주면서 계산해나가야 합니다.

하지만 balls-i와 share-i를 나누면 소수점을 가진 값이 나오므로

분자는 큰 값에서 작은 값으로, 분모는 작은 값에서 큰 값 순서대로 나눠서 최대한 숫자의 크기를 줄여야 해요.

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

| 풀이 2

풀이 1의 방법이 생각나지 않는다면 로직은 그대로 가져가면서 정수형 데이터 범주 값을 넘어서는 숫자를 계산할 수 있는 BigInteger 클래스를 사용할 수도 있습니다.

import java.math.*;
class Solution {
   public BigInteger solution(int balls, int share){
       return fac(balls).divide(fac(balls-share).multiply(fac(share)));
   }
   
   public BigInteger fac(int num){
       BigInteger ret = new BigInteger("1");
       BigInteger from = new BigInteger("1");
       BigInteger to = new BigInteger(String.valueOf(num));
       for(BigInteger i = from ; i.compareTo(to) <= 0 ; i= i.add(BigInteger.ONE)){
           ret = ret.multiply(i);
       }
       return ret;
   }
}

 

| 해설

굉장히 간단한 로직처럼 보이지만 모든 경우의 수를 충족하는 코드를 도출하기는 쉽지 않은 문제였습니다.

누구나 생각해 낼 수 있는 아이디어지만 누구나 해결할 수 없는 이런 문제 정말 매력적이네요.

문제가 잘 안 풀리면 주어진 예시를 풀어적어보세요.

그래도 안 풀린다면 주어진 숫자보다 더 큰 혹은 더 작은 수를 도입해 보세요.

모든 문제는 반드시 해결방법이 있으니 절대 포기하지 마세요.