문제
머쓱이는 구슬을 친구들에게 나누어주려고 합니다. 구슬은 모두 다르게 생겼습니다. 머쓱이가 갖고 있는 구슬의 개수 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
'🫧 코테 : CodingTest' 카테고리의 다른 글
[프로그래머스] Java : 가까운 수 (0) | 2024.03.17 |
---|---|
[프로그래머스] Java : 중복된 문자 제거(linkedHashSet) (1) | 2024.03.15 |
[프로그래머스] Java : 소인수분해(HashSet) (2) | 2024.03.14 |
[프로그래머스] Java : 최빈값 구하기 (0) | 2024.02.23 |
[프로그래머스] Java : 분수의 덧셈(최대공약수, 배열의 초기화) (1) | 2024.02.23 |