[프로그래머스 코딩테스트 연습] 구슬을 나누는 경우의 수

문제 설명

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

---

제한사항

• 1 ≤ balls ≤ 30
• 1 ≤ share ≤ 30
• 구슬을 고르는 순서는 고려하지 않습니다.
• share ≤ balls

---

입출력 예

balls	share	result
3	2	3
5	3	10

---

입출력 예 설명

입출력 예 #1

• 서로 다른 구슬 3개 중 2개를 고르는 경우의 수는 3입니다.

입출력 예 #2

• 서로 다른 구슬 5개 중 3개를 고르는 경우의 수는 10입니다.

---

Hint

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

---

※ 공지 - 2022년 10월 11일 제한 사항 및 테스트케이스가 수정되었습니다.

---

나는 컴공을 졸업했지만 문과출신 복수전공생이어서 수학을 잘 못한다.

 

그래서 문제에 힌트가 있는걸 보고 이런 생각을 했다

 

 

"펙토리얼 재귀함수를 만들어서 때려박으면 되겠구나!"

 

 

어림없는 소리. 테스트케이스는 통과했지만 제출을 누른 순간 무수한 런타임 에러와 실패들을 보며 절망에 빠졌다.

 

답을 맞추기 전까진 다른 사람의 풀이를 볼수 없기 때문에 나는 BigInteger의 존재를 몰랐고 long으로 타입을 변경해봐도 뜨는 런타임 에러와 실패를 보며 고민을 시작했다.

 

사실 고민은 길지 않았다. 검색해봤는데 다들 combination 로직을 만들어서 하더라....

 

근데 이걸 보고 그대로 따라하긴 싫었다. 애초에 풀이를 이해하지 못하고 사용하는게 무슨 의미가 있겠나 싶었다. 이게 테스트가 아니라 시험이었으면 에라 모르겠다 하고 써봤겠지만 공부하는 상황에서 이해하지 못한 풀이를 그대로 적는건 자기 발전에 도움이 안 될것 같았다.

 

그래서 직접 손으로 몇 문제 만들어 풀어봤는데...

 

이거맞아? 싶을정도로 진짜 쉬운 풀이법이 하나 보였다.

 

 

힌트를 잘 보면

 

분자의 경우 : n * n-1 * n-2 * n-3 ······ 3 * 2 * 1

분모의 경우 : (n-m* n-m-1 ······ 2 * 1) * (m* m-1 * m-2 * ······ * 2 * 1)

 

뭔가 보이지 않는가?

 

이걸 숫자로 보면 굉장히 쉬운 규칙이 하나 보이는데 n이 20, m이 5라고 가정하면

분자의 경우 : 20 * 19 * 18 * 17 * ······ * 3 * 2 * 1

분모의 경우 : (15 * 14 * 13 * 12 * ······ * 3 * 2 * 1) (5 * 4 * 3 * 2 * 1)

 

분모의 15! 은 분자와 함께 나눠 없앨수 있다. 이경우 식이 이렇게 바뀌고

분자의 경우 : 20 * 19 * 18 * 17 * 16

분모의 경우 : 5 * 4 * 3 * 2 * 1

 

이걸 코드로 바꾸면 이렇게 된다

class Solution {
    public int solution(int balls, int share) {
        long answer = 1;
        int shareIndex = 1;
        for(int i = share+1; i <= balls; i++){
            answer *= i;
            answer /= shareIndex;
            shareIndex++;
        }
        
        return (int)answer;
    }
}

 

share부터 시작해 balls까지 곱한 수를 1부터 시작해 share까지 곱한 수로 나누어주면 된다.

 

이 해답에 오류가 있을 수 있다면 answer / shareIndex가 정수가 아닌 경우인데 제출 및 채점에 오류가 없는걸 보니 문제가 바뀌지 않는 이상 문제 없어보인다.