[프로그래머스|JS] Lv.0 구슬을 나누는 경우의 수

https://school.programmers.co.kr/learn/courses/30/lessons/120840

프로그래머스

 

📌 문제 설명

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

 

제한사항

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

입출력 예

3	2	3
5	3	10

 

Hint

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

 

---

📌나의 풀이

1.  실패한 첫 번째 풀이

function solution(balls, share) {
    var answer = 0;
    //balls 갖고 있는 구슬 개수 => n
    //share 나눠 줄 구슬 개수 => m
    //서로 다른 n개 중 m개를 뽑는 경우의 수 
    //n! / (n-m)! * m!  => ! : 팩토리얼은 1부터 주어진 양의 정수까지의 모든 자연수의 곱
    //5!=5×4×3×2×1=120  5!는 1부터 5까지 곱셈 5번을 반복
    
    //분자
    let n = 1;  //n!: 팩토리얼 곱셈 값 저장할 변수 선언
    //분모
    let m1 = (balls-share);   // (n-m)! 값 저장할 변수 선언
    let m2 = 1;   // m! 값 저장할 변수 선언
    let m; // 최종 분모 값 저장할 변수
    
    //분자 팩토리얼 값 계산
    for(let i=1; i<=balls; i++){ //내가 가진 구슬 개수 만큼 반복
        //예) balls가 3일 때 1*1(i) -> 1*2(i) -> 2*3(i) => 6 (=1*2*3)와 같다.
        n *= i; 
    }
    
    //분모 팩토리얼 계산
    for(let k=1; k<=share; k++){ //나눠 줄 구슬 개수 만큼 반복
        m2 *= k; 
        
        //(n-m)!값 계산
        for(let j=1; j<=k-j; j++){ //share-2까지?
            //예를들어 3개에서 2개 고른다면 분모 계산은 (3-2)! * 2! => 1:곱셈0번 * (2*1):곱셈1번
            //5개에서 3개를 고른다면 (5-3)! * 3! => (2*1):1번 * (3*2*1):2번
            //--> 곱셈 반복 개수 규칙이 보임
            m1 *= j; 
        }
    }
    
    m = m1 * m2;
    
    answer = n / m;
    
    return answer;
}

 

처음에 팩토리얼을 까먹어서 검색을 해야했고 문제 이해하고 어떻게 로직을 짜야할지 고민만 30분은 소요한 것 같다.

테스트 코드 실행은 통과! 하지만 채점 결과 35개의 테스트중 4개만 통과고 나머지는 다 실패했다. 😧

문제 원인

• (n-m)! 값을 구하는 로직이 잘못됨. m1은 (balls - share)!의 값을 계산해야 하는데, 이 부분에서 중첩된 for문이 잘못된 방식으로 사용중이었다.
• for(let j=1; j<=k-j; j++){ 이 부분의 조건이 논리적으로 맞지 않았음. 결국 작동하지 않아서 문제! (+ j <= share-2 또한 실패)

해결책:

1. 팩토리얼 계산을 분리하여 구현:

• n!, (n-m)!, m! 팩토리얼을 구하는 코드를 별도의 함수로 만들기
• n! (분자)와 (n-m)! * m! (분모)를 분리하여 계산하기

 

2.  두번째 풀이

function solution(balls, share) {
    var answer = 0;
    
    //balls = n
    //share = m
    //서로 다른 n개 중 m개를 뽑는 경우의 수 공식 : n! / (n-m)! * m! 
    
    //분자
    let n = factorial(balls);  //n! 값
    //분모 
    let m1 = factorial(balls-share);   // (n-m)! 값 
    let m2 = factorial(share);   // m! 값 
    
    answer = n / (m1*m2) ; // 경우의 수 공식 계산
    
    return answer;
}

//팩토리얼 계산 함수
function factorial(number){
    
    let result = 1;
    
    for(let i=1; i<=number; i++){
        result *= i;
    }
    
    return result;
}

 

수정한 풀이로 테스트 코드는 성공했지만 채점 결과는 실패했다.

정확성: 80.0
합계: 80.0 / 100.0

 

문제 원인

• 공식 계산 결과가 소수점 이하의 수로 나올 경우에 대해 처리를 안함

예를 들어, n=5이고, m=3일 때 공식의 계산 결과는 10.0이 되고,
n=30이고 m=20m = 20m=20일 때 공식의 계산 결과는 30,045,015.0이 된다.

JavaScript에서 정수 간의 계산 이라고 하더라도,
큰 수의 나눗셈 에서는 부동소수점 방식으로 처리되기 때문에 소수점 이하의 매우 작은 값이 생길 수 있습니다.
이로 인해 소수점이 생길 수 있으며, 이는 실제로는 계산 오차입니다.
(소수점이 생기는 원인은 부동소수점 오차)

 

 

 

왜 소수점이 발생할까? 

1. JavaScript의 부동소수점 연산: JavaScript는 IEEE 754 표준을 따르는 64비트 부동소수점으로 숫자를 처리합니다. 따라서 매우 큰 수를 다룰 때는 연산 중 소수점 이하의 작은 오차가 발생할 수 있습니다.
2. 팩토리얼 계산에서의 큰 값: 팩토리얼 계산 시, 값이 매우 커지면서 나눗셈 연산이 부정확하게 될 수 있습니다. 결과적으로, 아주 작은 소수점이 추가되어 실제로는 정수여야 할 값에 소수점이 붙는 경우가 발생할 수 있습니다.

 

 

해결책:

1. Math.round() 사용

• 보통 부동소수점 오차가 있는 경우 사용하기 적절하다.
• 예를 들어, 9.99999999나 10.0000001처럼 실제로는 정수여야 하는 값이 소수점 자리에서 미세한 오차가 생긴 경우.

구슬 5개 중 3개를 고르는 경우의 수가 10이어야 하지만, 계산 과정에서 10.00000000001이나 9.99999999999처럼 나올 수 있기 때문에 이 경우 Math.round()를 사용해서 이를 10으로 정확히 맞춰줍니다.

Math.floor() 또는  Math.ceil()을 사용하면 계산 결과가 의도적으로 변형될 수 있습니다.
예를 들어, 경우의 수는 정수여야 하므로 floor를 사용하면 실제 경우의 수보다 적은 값으로 처리될 수 있고,
ceil을 사용하면 경우의 수보다 더 큰 값으로 계산될 수 있습니다.

 

 

 

 

마지막에 리턴 값에 Math.round()를 사용해서 정수로 맞춰주고 통과할 수 있었다.

return Math.round(answer);

 

 

 

📌다른 풀이

1. 재귀함수를 사용하여 팩토리얼 계산 

*재귀함수는 자기 자신을 호출하는 함수입니다. 즉, 함수가 자신의 이름을 사용하여 다시 호출되는 방식입니다.
이 방식은 특정 문제를 더 작은 문제로 나누어 해결할 때 유용하게 사용합니다.

const 팩토리얼 = (num) => num === 0 ? 1 : num * 팩토리얼(num - 1)

function solution(balls, share) {
  return Math.round(팩토리얼(balls) / 팩토리얼(balls - share) / 팩토리얼(share))
}

 

'팩토리얼' 함수 동작 

• 만약 num이 0이면, 1을 반환합니다. (수학에서 0!=10! = 10!=1이기 때문입니다.)
• 그렇지 않으면, num에 팩토리얼(num - 1)을 곱해 줍니다.
  • 예를 들어, 팩토리얼(3)을 호출하면:
    • 3이 0이 아니니, 3×팩토리얼(2)3 \times \text{팩토리얼}(2)3×팩토리얼(2)를 계산합니다.
    • 팩토리얼(2)도 0이 아니니 2×팩토리얼(1)2 \times \text{팩토리얼}(1)2×팩토리얼(1)을 계산하고,
    • 팩토리얼(1)도 0이 아니니 1×팩토리얼(0)1 \times \text{팩토리얼}(0)1×팩토리얼(0)을 계산합니다.
    • 팩토리얼(0)이 1이니, 결국 1을 곱해서 3×2×1=63 \times 2 \times 1 = 63×2×1=6을 얻게 됩니다.