[프로그래머스] (Java) 구슬을 나누는 경우의 수 문제풀이

 

 

📑 1. 문제설명

 
입출력 예

balls	share	result
3	2	3
5	3	10

 
입출력 예 설명
 
입출력 예 #1

• 서로 다른 구슬 3개 중 2개를 고르는 경우의 수는 3입니다.

 
입출력 예 #2

• 서로 다른 구슬 5개 중 3개를 고르는 경우의 수는 10입니다.

---

💡 2. 접근방식

이 문제는 조합(combination) 문제이다.  조합을 배운 지 오래되서 검색하면서 풀었다.
 
주어진 balls개의 구슬 중에서 share개의 구슬을 고르는 경우의 수를 구하는 문제이다.
조합을 구하는 공식이 문제 힌트로 주어져 있다.

• n은 전체 개수 (balls)
• m는 고를 개수 (share)

이것을 문제에서 주어진 매개변수로 변환하면 아래와 같다.   

조합(Combination) 공식

 팩토리얼 함수를 만들어서 공식을 코드로 구현하면 된다. 조합 계산을 할 때 팩토리얼 값이 커지면 매우 큰 수가 나와서 오버플로우가 발생할 가능성이 있기 때문에 int로 직접 계산하지 않고  BigInteger를 사용한다.

import java.math.BigInteger;

class Solution {
    public int solution(int balls, int share) {
        return (int) (factorial(balls).divide(factorial(share).multiply(factorial(balls - share))).longValue());
    }
    
    // 팩토리얼을 계산하는 함수
    public BigInteger factorial(int n) {
        BigInteger result = BigInteger.ONE;
        for (int i = 1; i <= n; i++) {
            result = result.multiply(BigInteger.valueOf(i));
        }
        return result;
    }
}

 
한 편, 이 문제는 순열 공식을 조합공식으로 바꾸는 법을 써도 된다.
 
순열과 조합의 차이

• 조합(Combination)  이란 "순서 상관없이 몇 개를 고르는 방법" 
• 순열(Permutaion) 이란 "순서를 고려해서 몇 개를 고르는 방법" 

⭐ 순열(Permutation) 공식을 조합(Combination) 공식으로 변환하면 이 문제를 쉽게 풀 수 있다.

 

순열(Permutation) 공식

조합(Combination) 공식

= 조합은 순열을 먼저 구한 후, 중복으로 세어진 경우를 나누어서 구할 수 있다.
왜냐하면 조합 공식은 분모에 r!이 한 번 더 들어가므로 순열 공식을 r!로 한번 더 나누면 조합 계산식이 된다.
 
📌 예를 들어서 입출력 예 #2 처럼 5개중 3개를 뽑는 경우에 대해 생각 해 보자.

순열(순서 고려)

 
여기까지가 `answer *= (balls - (share - i));` 부분이다.

• 1회차 (i = 1) → answer = 5
• 2회차 (i = 2) → answer = 5 × 4 = 20
• 3회차 (i = 3) → answer = 5 × 4 × 3 = 60

✔️ 즉 여기까지 순열 공식으로 계산한 결과는 60이다. 이것을 조합으로 바꾸려면 중복된 경우(3!)로 나눈다. 그럼 결과값 Combination 결과값인 10을 얻을 수 있다.
 

조합(순서 제거)

 
 

👨‍💻 3. 정답코드

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

 
틀렸대 ㅠㅠ 오늘은 자고 내일 다시 하기

---

🐦4. 오답정리

이 문제에서 `balls`와 `share`의 범위가 1부터 30 사이여서 비교적 작은 숫자로 보일 수 있지만, 조합 계산 과정에서 정수 오버플로우(Integer Overflow)가 발생하여 정확도가 100%가 되지 않는 것이다. 

 

조합(Combination) 공식

예를 들어, `balls = 30`, `share = 15`인 경우 

 

 

팩토리얼을 수행하면서 곱셈 과정에서 `answer *= (balls - (share - i))`에서 answer가 점점 커지기 때문에 `int(32비트, 약 21억)` 범위를 초과하는데 이 때, 자바의 int는 오버플로우가 발생해도 오류를 내지 않고 잘못된 값으로 변형된다. 만약 오버플로우로 인해 answer 값이 잘못되면, 이후 answer /= i;을 계산할 때 나눗셈에도 값이 정확하게 반영되지 않아서 정상적인 결과를 얻을 수가 없다.

 

이를 해결하기 위해 long을 사용하거나, BigInteger를 활용해야 한다. 

 

해결 방법

 

1. int를 long으로 바꾸기

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

 

2. ( 안전한 방법) int를 BigInteger로 바꾸기

import java.math.BigInteger;

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

BigInteger를 사용하면 오버플로우 걱정 없이 큰 수 연산이 가능하다.