[ 프로그래머스 ] 구슬을 나누는 경우의 수 ( JS )

 

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

프로그래머스

 

---

[ 문제 ]

 

 

[ 내 풀이 ]

function solution(balls, share) {
    // 팩토리얼을 계산하는 재귀 함수
    const factorial = a => {
        if(a === 0 || a === 1) return 1; // 0!과 1!은 1로 정의됨
        return a * factorial(a - 1); // n! = n * (n-1)!
    }
    
    const a = factorial(balls); // balls의 팩토리얼
    const b = factorial(share); // share의 팩토리얼
    const ab = factorial(balls - share); // (balls - share)의 팩토리얼
    
    // 조합 계산: nCr = n! / (r! * (n-r)!)
    return Math.round(a / (ab * b)); // 조합 값을 계산하고 반올림하여 반환
}

 

 

[ 다른 풀이 ]

// 팩토리얼 함수를 정의
const 팩토리얼 = (num) => num === 0 ? 1 : num * 팩토리얼(num - 1);

// 주어진 공의 개수와 나눠줄 개수를 입력받아 조합을 계산하는 함수
function solution(balls, share) {
  // 조합을 계산하는 공식: nCr = n! / (r! * (n-r)!)
  // Math.round를 사용하여 계산 결과를 반올림
  return Math.round(팩토리얼(balls) / 팩토리얼(balls - share) / 팩토리얼(share));
}

// 예시 1: Math.round를 사용한 경우
console.log(solution(5, 3));  // 결과: 10

// 예시 2: Math.round를 사용하지 않은 경우 (반올림 제거)
console.log(팩토리얼(5) / (팩토리얼(3) * 팩토리얼(5 - 3)));  // 결과: 10.000000000000002


// < 설명 >
// 조합 계산에서는 소수점 이하의 오차가 발생할 수 있습니다.
// Math.round를 사용하면 이러한 오차를 반올림하여 정수 결과를 얻을 수 있습니다.
// 예를 들어, Math.round를 사용하지 않을 경우 소수점 이하의 아주 작은 값이 남아 있을 수 있어
// ..정확한 결과를 얻기 어려울 수 있습니다.
// Math.round를 사용하면 이를 반올림하여 정확한 조합 개수를 얻을 수 있습니다.

function solution(balls, share) {
  // 주어진 공의 개수와 나눠줄 개수를 변수에 할당
  const [n, m] = [balls, share];

  // 팩토리얼 값을 저장할 배열 초기화 (fact[0] = 1, fact[1] = 1)
  const fact = [BigInt(1), BigInt(1)];

  // 팩토리얼 계산: 2부터 n까지의 팩토리얼 값을 배열에 저장
  for (let i = 2; i <= n; i++) fact[i] = fact[i - 1] * BigInt(i);

  // 조합 계산: nCr = n! / (r! * (n-r)!)
  // BigInt를 사용하여 큰 수를 처리하고, 최종 결과를 Number 타입으로 변환
  return Number(fact[n] / (fact[n - m] * fact[m]));
}

// BigInt에 대한 설명:
// JavaScript에서 정수의 범위는 Number 타입으로 표현될 때 제한이 있습니다 (안전한 정수 범위: -(2^53 - 1)에서 2^53 - 1).
// BigInt는 이보다 큰 정수를 표현할 수 있도록 도와주는 데이터 타입입니다.
// 예를 들어, 팩토리얼 계산과 같은 큰 수를 다룰 때 BigInt를 사용하면 정밀도를 유지할 수 있습니다.
// BigInt는 숫자 리터럴 끝에 'n'을 붙여서 생성할 수 있으며, 예를 들어 BigInt(123) 또는 123n과 같이 사용할 수 있습니다.
// BigInt는 기본 산술 연산자(+,-,*,/,%)를 사용할 수 있지만, Number 타입과 혼용해서 사용할 수는 없습니다.
// 따라서, BigInt로 계산된 값을 다시 Number로 변환하려면 명시적으로 변환해야 합니다 (예: Number(bigIntValue)).

 

[ 참고 자료 ]

https://joooing.tistory.com/entry/Javascript-%EC%86%8C%EC%88%98%EC%A0%90floating-point-%EA%B3%84%EC%82%B0-%EC%98%A4%EB%A5%98

Javascript 소수점 오류 원인, 해결방안