[프로그래머스][java] lv 0 구슬을 나누는 경우의 수

1. 문제 설명

 

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

2. 나의 풀이

class Solution {
    public int solution(int balls, int share) {
        int denominator = 1;
        int numerator = 1;   
        int temp = 1;
        
        for(int i = 1; i <= balls; i++)
		{
        	denominator *= i;// balls의 팩토리얼. 분자가 될 부분
        	
        	if(i <= share)
			{
        		numerator *= i;// share의 팩토리얼. 분모가 될 부분
        		
        		if(i <= (balls -share))
        		{
        			temp *= i;//balls- share의 팩토리얼 
        		}
			}
		}
        return denominator/(numerator*temp);
    }
}

처음에 이렇게 푼 다음에 성공인 줄 알았다.

하지만 제출 후 테스트에서 반은 실패..!! 왜지!?!

실패한 이유

 

• denominator, numerator, temp 변수의 계산이 팩토리얼 계산 순서상 의도대로 작동하지 않을 가능성이 있음.
• 팩토리얼 계산 시 값이 커지면서 int 범위를 초과하여 잘못된 결과를 반환할 가능성.
• 필요하지 않은 팩토리얼 전체를 계산하여 비효율적임.

 

아하.. 팩토리얼 계산하면서 int 범위를 넘었다..

public static int solution(int balls, int share) {
		
        if (share > balls / 2) {
            share = balls - share; // 대칭성을 이용해 최적화
        }

        long result = 1;
        
        for (int i = 0; i < share; i++) {
            result *= (balls - i); // 분자 계산
            result /= (i + 1);     // 분모 계산
        }
        return (int)result;
    }

1.(n-m)!을 하는 이유는 경우의 수를 제거하기 위함임.
그런데 r개를 고르는 것과 n-r개를 고르는 것은 동일한 경우의 수를 가짐.
r개를  고르면 n-r개가 자연스럽게 남게 되기 때문임.

예시 :

// 5!/(5-3)! * 3! => 5!/ 2!* 3!
// 5!/(5-2)! * 2! => 5!/ 3!* 2!

그러므로 share > balls / 2 라면  

share을 그대로 쓰는 것 보다 연산을 줄일 수 있는 balls - share; 으로 하는 게 낫다.

2.  result가 long 타입인 이유는 팩토리얼 연산 범위가 int 를 넘을 수 있기 때문.

3.         for (int i = 0; i < share; i++) {
            result *= (balls - i); // 분자 계산
            result /= (i + 1);     // 분모 계산
        }

이건 어디서 나온거냐면?

5개 중 3개를 고르는 경우를 가정하면 식이 이렇게 성립된다

이 중 분모와 분자의 중복되는 항목인 3×2×1을 서로 취소할 수 있다.

각 분자와 분모를 미리 연산한 뒤 분수로 만들지 않고,

share의 숫자 만큼만 분자/분모의 연산을 하면 자연스럽게 뒤에 나오는 중복되는 항목(3!)은 계산하지 않는것이다.

분자는 5에서부터 하나씩 줄어야 하니 balls - i

분모는 1에서부터 늘어야 하므로 i+1이다.

3. 다른 사람의 풀이

class Solution {
    public long solution(int balls, int share) {
        long answer = 0;

        int d = (balls - share) > share ? share : balls - share;
        if (d == 0) return 1;

        return solution(balls - 1, d - 1) * balls / d;
    }

}

1. d == 0 (share = 0 ||  balls - share = 0 )

5개에서 0개를 고름 => 경우의 수 1개

5개에서 5개를 고름 => 경우의 수 1개 

즉 return 1

2. return solution(balls - 1, d - 1) * balls / d; (재귀함수 호출)

예를 들어, solution (5,3)의 계산이면

• 첫 번째 호출: solution(5, 3) → d = 2 (왜냐하면 min(5 - 3, 3) = 2)
• 두 번째 호출: solution(4, 2) → d = 2
• 세 번째 호출: solution(3, 1) → d = 1
• 네 번째 호출: solution(2, 0) → 종료 조건에 도달하여 1을 반환

위 풀이와 같이 분자와 분모의 계산을 하나씩 수행하는 것이다.

즉 풀이를 요약하면

• 대칭성을 활용하여 계산.
• 재귀 함수를 사용하여 C(n,r)을 분할해서 계산하고, 재귀 호출을 통해 점진적으로 결과를 구함.
• 종료 조건은 C(n,0) 또는 C(n,n)이 1이라는 특성을 이용.

이 함수는 재귀적 방식으로 조합을 효율적으로 구하는 방식임.