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

Janet·2023년 4월 4일
0

Algorithm

목록 보기
108/314

문제 설명

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


제한사항

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

입출력 예

ballsshareresult
323
5310

입출력 예 설명

입출력 예 #1

  • 서로 다른 구슬 3개 중 2개를 고르는 경우의 수는 3입니다. https://grepp-programmers.s3.ap-northeast-2.amazonaws.com/files/production/668adf7a-38b1-4112-bbc5-4fab429168c9/%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202022-08-01%20%E1%84%8B%E1%85%A9%E1%84%92%E1%85%AE%204.15.55.png

입출력 예 #2

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

Hint

  • 서로 다른 n개 중 m개를 뽑는 경우의 수 공식은 다음과 같습니다. https://grepp-programmers.s3.ap-northeast-2.amazonaws.com/files/production/54c8b2b9-f88c-4a09-8956-7560ff7ea918/%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202022-08-01%20%E1%84%8B%E1%85%A9%E1%84%92%E1%85%AE%204.37.53.png

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


문제풀이

💡 문제풀이 과정

  • Hint로 받은 서로 다른 n개 중 m개를 뽑는 경우의 수 공식은 조합의 공식이다. 공식에서 나오는 n!!팩토리얼(factorial) 기호로, factorial이란 수학적 용어로 계승을 의미하며, 서로 다른 n개를 나열하는 경우의 수 이다.
    • n! = n(n-1)(n-2)(n-3) … 1
    • 5! (5의 계승) = 5 4 3 2 1 = 120
  • 조합(nCr, Combination)이란 서로 다른 n개 중에 r개를 선택하는 경우의 수를 의미한다. 조합은 뽑는 순서가 중요하지 않다. 순열(nPr, Permutation)과 비슷하지만, 순열의 경우 뽑는 순서가 중요하다. 순열 또한 서로 다른 n개 중에 r개를 선택하는 경우의 수를 의미한다.
    • 조합(nCr) = n! / (n-r)! * r!
    • 순열(nPr) = n! / (n-r)!

  • 답안 1번: while()을 사용하여 share가 0이 되기 전까지 -1을 하여 팩토리얼 공식을 대체하였다. 리턴 부분에서 Math.round()를 한 이유는 테스트의 반례로 결과값이 소수점이 되는 경우가 있어 반올림을 하여 리턴 하였다.
  • 답안 2번: 재귀함수를 사용한 다른 사람의 풀이이다.
  • 답안 3번: [BIgInt()]for() 반복문을 사용하여 공식을 풀이하였다. BigInt
    는 Number원시 값이 안정적으로 나타낼 수 있는 최대치인 2^53 - 1보다 큰 정수를 표현할 수 있는 내장 객체이다. BigInt는 정수 리터럴의 뒤에 n을 붙이거나(10n) 함수 BigInt()
    를 호출해 생성할 수 있다. BigInt와 Number는 차이가 있는데,  BigInt는 내장 Math 객체의 메서드와 함께 사용할 수 없고, 연산에서 Number와 혼합해 사용할 수 없다. 따라서 먼저 같은 자료형으로 변환해야 한다. 그러나, BigInt가 Number로 바뀌면 정확성을 잃을 수 있으니 주의해야 한다.
    - BIgInt() 관련 출처 및 자세한 내용: https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/BigInt

✅ 답안 #1

function solution3(balls, share) {
  let answer = 1;
  while (share) {
    //share가 0이 되기 전까지
    answer *= balls / share;
    balls--;
    share--;
  }
  return Math.round(answer);
}

✅ 답안 #2

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

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

✅ 답안 #3

function solution(balls, share) {
  let factorial = [BigInt(1)];
  for (let i = 1; i <= balls; i++) {
		factorial[i] = factorial[i - 1] * BigInt(i);
	}
  return factorial[balls] / (factorial[balls - share] * factorial[share]);
}
profile
😸

0개의 댓글