[프로그래머스 입문][자바] 구슬을 나누는 경우의 수

❓문제설명

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

프로그래머스

 

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

---

제한사항

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

---

 

입출력 예

balls	share	result
3	2	3
5	3	10

 

---

입출력 예 #1

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

  

입출력 예 #2

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

---

Hint

• 서로 다른 n개 중 m개를 뽑는 경우의 수 공식은 다음과 같습니다. 

  

---

🔍문제해석

어떤걸 풀어야 할까?

1. 구슬의 전체 수와 친구한테 나눠줘야하는 수, 골라야 하는 구슬의 수가 주어지면 전체 수 중에 n개의 구슬을 집는 경우의 수를 구하라.

2. {a,b} ,{b,a} 등의 중복은 허용되지 않는다. 서로 다른 구슬을 골라야한다.

 

---

🧐문제풀이

• 문제 풀이 구상

문제에 이미 경우의 수를 구하는 공식이 떡하니 있어서 바로 대입해서 코드를 작성하였다.

class Solution {
    public int solution(int balls, int share) {

        int answer = 0;
        answer = combination(balls, share);
        return answer;
    
    }
     public int combination(int n, int m) {
        return factorial(n) / (factorial(n - m) * factorial(m));
    }

    public int factorial(int num) {
        if (num == 0 || num == 1) {
            return 1;
        }
        int result = 1;
        for (int i = 2; i <= num; i++) {
            result *= i;
        }
        return result;
    }
}

 

힌트로 준 식으로 작성한 코드는 전체  케이스 중에 절반도 통과하지 못했다..

 

result *= i;

이렇게 계속 곱하는 코드로 인해 int의 범위를 넘어가기때문에 long으로 return하는 걸로 변경해봤지만

정확성이 조금 올라갈뿐, 실패하기는 매한가지였다.

더 큰 수를 담기위해 타입을 BigInteger로 바꾸는 방식도 많이 보았다.

하지만 애초에 정해져있는 return 타입을 바꾸어야만 풀 수 있는 문제인지 생각해보았고, 다른  방법을 찾아보기로 하였다.

 

int와 long, BigInteger

	int	long	BigInteger
크기	32비트(4바이트)	64비트(8바이트)	가변적
값의 범위	-2,147,483,648 ~ 2,147,483,647	-9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807	Integer.MAX_VALUE보다 큰 정수도 저장 가능
비고	기본 데이터 타입	기본 데이터 타입	java.math.BigInteger 클래스에 정의된 참조 데이터 타입

.

.

.

문제의 힌트는 사실 fake였다. 식을 내어줌으로써 꼭 이 식을 사용해야만 할 것 같았지만 이 문제는 조합 알고리즘을 이용해서 풀어야 하는 것이었다.

C(n, r) = C(n−1, r−1) + C(n−1, r)

 

n에서 r를 구하는 수 ( C(n,r) ) =

      현재 원소를 선택하여 나머지 r - 1 개를 선택하는 경우( C(n - 1, r - 1) )

   + 현재 원소를 선택하지 않고 나머지 r개를 선택하는 경우(C(n - 1, r))

 

 

• 알고리즘 선택

조합 (combination)을 이용하여 풀었다.

---

！제출코드

1. 중복없는 조합을 구하기 위한 메소드 호출

2. 전체수와 구하는 수가 같거나 구하는 수가 0이라면 조합의 경우의 수는 1이다.

3. 현재 원소에서 하나를 선택하여 전체수-1에서 (구하는 수 -1)개의 수를 선택하는 경우 + 현재 원소중에서 선택하지 않고 나머지 r개의 수를 선택하는 경우

class Solution {
    public int solution(int balls, int share) {

        int answer = 0;
        // (1)
        answer = combination(balls, share);
        return answer;
    
    }
    public int combination(int n, int r ){
        // (2)
        if(n == r | r == 0)  return 1;
        // (3)
        else return combination(n-1,r-1) + combination(n-1,r);
    }
}