이전까지는 매일 여러 문제를 풀었지만, 앞으로는 포스팅을 할 때 한 문제씩 좀 더 깊이 있게 다루려 한다.

구슬을 나누는 경우의 수

문제

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

입출력 예

balls	share	result
3	2	3
5	3	10

풀이

접근방법

이 문제의 핵심은 조합(Combination)이다. 조합이란 n개의 서로 다른 원소 중에서 r개를 선택하는 경우의 수를 말한다. 조합의 공식은 다음과 같다.

C(n, r) = n! / [(n-r)! * r!]

이 공식을 활용해서 문제를 풀었다. 팩토리얼이 있는데 팩토리얼은 n부터 n-1까지의 곱을 이야기 한다. 코드 풀이는 아래에 있다.

코드

function factorial(n) {
    if (n === 0) {
        return 1;
    }
    return n * factorial(n - 1);
}

function solution(balls, share) {
    return Math.round(factorial(balls) / (factorial(share) * factorial(balls - share)));
}

핵심은 재귀함수를 활용해서 푼 것이다. 재귀함수란 함수에서 스스로 자신을 호출하는 걸 말한다. 코드를 보면 factorial 함수가 재귀함수다.

재귀함수에서 가장 중요한 건 n이 0이 됐을 때 함수에서 나올 수 있도록 하는 것이다. 그래서 factorial 함수를 보면 n이 0일 때 1을 리턴해서 함수를 마무리 지었다. 만약 처음 balls가 3일 경우 3 x 2 x 1 이 돼서 6이 된다.

마지막으로 풀이함수를 보면 조합(Combination) 공식과 팩토리얼 함수를 사용해서 풀었다. round를 사용한 이유는 값이 소수점이 나올 경우를 처리해줘야 되기 때문이다. floor나 ceil을 사용하면 조합의 경우가 올바르게 나오지 않는다.

정리하기

코딩 기초 트레이닝을 마무리하고 코딩 입문에 들어갔다. 지금까지는 막무가내, 피지컬로 어느 정도 문제를 풀 수 있었다. 그러나 이제는 그렇게 풀면 안되고, 수학적인 사고와 분석적인 사고를 요구한다. 그래서 공식과 알고리즘과 같은 것이 중요하기 때문에 앞으로는 한 문제 한 문제 진중하게 포스팅하려 한다.

이번 문제는 조합 공식에 관한 문제다. 그러나 단순히 공식을 적용하는 것이 아니라 팩토리얼을 재귀함수로 다룰 줄 아는 걸 요구했. 그래서 조합에 가능성에 대한 문제를 마주할 경우 이번 문제를 떠올리면 좋을 것 같다.