Algorithm/프로그래머스

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

OnnJE 2022. 12. 13. 17:53
반응형

문제 설명

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

제한사항

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

 

풀이

function solution(balls, share) {
    if (share === 0) return 1
    return  factorial(balls) / (factorial(balls - share) * factorial(share))
}

function factorial(n) {
    let re = BigInt(1)

    for (let result = 2; result <= n; result++) {
        re *= BigInt(result)
    }
    return re
}

 

사고과정

  1. 재귀를 이용해 팩토리얼 함수를 선언한다
  2. 팩토리얼 함수를 이용해 조합 공식을 풀면 되겠다
  3. 에러가 뜨네?
  4. js 특성상 수가 너무 커 int 범위에서 벗어날 경우 오류가 발생할 수 있다.
  5. 보다 큰 수를 담을 수 있는 bigint를 사용하자

 

평가

 

function solution(balls, share) {
    if (share === 0) return 1
    return  Math.floor(factorial(balls) / (factorial(balls - share) * factorial(share)))
}

function factorial(n) {
    if (n <= 1) return 1
    return n * factorial(n - 1)
}
const 팩토리얼 = (num) => num === 0 ? 1 : num * 팩토리얼(num - 1)

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

 

 

 위 첫 번째 코드는 사고과정 (2)에서 작성한 코드이며 큰 수에 대해 오류가 발생했다. js 정수형이 감당할 수 없는 큰 수로 인해 문제가 발생함을 깨달았고 풀이에서와 같은 코드로 고쳤다. 두 번째 코드는 다른 사람의 풀이 중 간략한 풀이를 가져온 것이다. factorial 함수의 구조도 거의 동일하다고 볼 수 있고 차이점은 나와 달리 Math.round를 적용한 것뿐이다.

  내가 생각하기에 조합 연산 결과가 소수점 아래 값을 가진다면 내림하는 게 맞는데 왜 반올림하는 게 옳은 정답을 내놓는 것일까? 이 부분은 정확한 정답을 아직 찾지 못했으며 조금 더 가까운 정수로 변환해주는 만큼 정답으로 처리하는 것인가 짐작만 하고 있다.

 

개선점

 

 

알게된점

  1. js에선 큰 수로 인해 오류가 발생할 수 있다.
  2. js의 큰 수에 대해선 bigint()로 대처 가능하며 bigint는 bigint끼리만 연산 가능하다. 단, 비교는 상관없다.
반응형