본문 바로가기
🫧 코테 : CodingTest

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

by 예옹이 2024. 3. 4.

 

문제

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

 

입출력 예

balls share result
3 2 3
5 3 10

 


 

이번 문제도 기억해두고 싶어서 이렇게 작성해봅니다. 

문제를 푸는 법은 우리가 많이 배웠던 확률과 통계에서 C(Combination)를 떠올리시면 됩니다. (ex. 5C2, 7C2)

 

 

이 형태의 식인거 다들 기억하시죠?

이 식을 약분해보겠습니다.

 

 

그럼 이런 형태가 만들어집니다. (n-m)!을 약분한 상태입니다.

이 구조를 코드로 구현하시면 됩니다.

 

 

+)

int는 32비트이고 이 값을 넘어가는 answer가 생길 수 있습니다.

그래서 solution과 answer 모두 long 타입으로 지정해 오버플로우를 해결해주었습니다.


 

코드

class Solution {
    public long solution(int balls, int share) {
        long answer = 1;
        
        for(int i=0; i<share; i++){
            answer *= (balls - i); // 분자 : n부터 n-m+1까지 나눔
            answer /= (i + 1); // 분모 : 1부터 m까지를 나눔
        }
        
        return answer;
    }
}

 

 

 

제가 푼 코드는 아래에서 확인하실 수 있습니다.

https://github.com/eonwy/programmers

 

GitHub - eonwy/programmers: 🔎 coding-test (programmers) 🔍

🔎 coding-test (programmers) 🔍. Contribute to eonwy/programmers development by creating an account on GitHub.

github.com