문제
머쓱이는 구슬을 친구들에게 나누어주려고 합니다. 구슬은 모두 다르게 생겼습니다. 머쓱이가 갖고 있는 구슬의 개수 balls와 친구들에게 나누어 줄 구슬 개수 share이 매개변수로 주어질 때, balls개의 구슬 중 share개의 구슬을 고르는 가능한 모든 경우의 수를 return 하는 solution 함수를 완성해주세요.
- 제한사항
- 1 ≤ balls ≤ 30
- 1 ≤ share ≤ 30
- 구슬을 고르는 순서는 고려하지 않습니다.
- share ≤ balls
풀이
- 오답
순열과 조합 중 조합에 해당하는 문제였다. 힌트 공식을 참고해 문제를 풀고 테스트 케이스를 통과해 제출을 했는데 상당수 통과하지 못했다.
1 ≤ balls ≤ 30 조건을 무심코 지나쳤는데, 30에서 1까지를 다 곱한다고 했을 때 선언한 변수들이 정수 오버플로우로 예상과 다른 값을 가질 가능성이 있겠다고 판단했다. 따라서 2가지를 변경하여 조금 더 효율적으로 코드를 작성했다.
class Solution {
public int solution(int balls, int share) {
int ballsX = 1;
int shareX = 1;
int minusX = 1;
for(int i=balls; i>=1; i--){
ballsX *= i;
}
for(int i=share; i>=1; i--){
shareX *= i;
}
for(int i=(balls - share); i>=1; i--){
minusX *= i;
}
return ballsX / (minusX * shareX);
}
}- 정답
첫 번째는 경우의 수를 나누어 주었다.
- 나누어 주어야 하는 개수와 가진 개수가 같을 때 경우의 수는 1이다.
- ★나누어 주어야 할 개수가, 가진 개수에서 나누어 주어야 하는 개수를 뺀 값보다 크다면 두 값 중 작은 값을 사용★한다.
2번 경우, 대체 무슨 말인지 헷갈릴 수 있다. 나의 경우 순열과 조합의 개념이 잘 기억나지 않아 공부하다가 힌트를 얻었다.
예를 들어 ball = 10, share = 7이라 해보자.
이때 ball - share은 3으로 share > ball - share 조건에 해당한다.
그렇다면 이 경우 작은 값인 3을 share에 대입해 계산식에서 사용하는 것이다.
가능한 이유는 10개 중 7개를 고르는 경우의 수와 3개를 고르는 경우의 수가 같기 때문이다.
ex. 7개 : 10! / 3! * 7! = 3개 : 10! / 7! * 3!
따라서 루프로 순회를 하며 팩토리얼(!)을 계산한다고 할 때, 둘 중 작은 값을 활용한다면 계산 효율성을 높일 수 있게 된다.
두 번째는 for문을 한 번만 사용하는 것이다.
아무리 생각해도 for문을 3개나 사용하는 것은 비효율적이라 느껴져 대폭 수정했다. 제일 먼저 for문 안에서 초기식 int i가 의미하는 것은 나누기 위해 선택한 개수이다.
이에 따라 현재까지 선택한 구슬의 개수를 전체 구슬의 개수에서 뺀 balls - i는 선택되지 않은 구슬의 개수를 의미하게 되며, 이를 곱해 변수 long combi에 누적해 주면 분자를 계산할 수 있게 된다.
ex. 10! = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 중 10 * 9 * 8에 해당하며 나머지는 분모의 7!에 의해 지워짐
그리고 구한 분자를 분모에 해당하는 i+1로 나누어 주면 조합 공식을 구현해 원하는 값을 구할 수 있게 된다.
ex. (n - m)!에 해당하는 값 3! = 3 * 2 * 1을 구현한 것
마지막으로 정수 오버플로우를 막기 위해 long 타입으로 선언했던 변수 combi를 (int)로 파싱한 뒤 반환하면 끝이다.
class Solution {
public int solution(int balls, int share) {
if (balls == share) {
return 1;
}
if (share > balls - share) {
share = balls - share;
}
long combi = 1;
for (int i=0; i<share; i++) {
combi *= balls - i;
combi /= i + 1;
}
return (int) combi;
}
}
결과
