[programmers] 구슬을 나누는 경우의 수, 중복된 숫자 개수, 배열의 평균값, 진료 순서 정하기, 팩토리얼

📝 [Lv0] 구슬을 나누는 경우의 수

👀 문제 설명

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

 

🚨 제한 사항

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

 

💻 입출력 예

balls	share	result
3	2	3
5	3	10

 

✨ 풀이 설명

두 가지 풀이 방법이 있다. 첫 번째로는 문제에서 말한 대로 팩토리얼을 구해 계산하는 방법이고, 두 번째는 조합을 파스칼의 삼각형을 이용해 푸는 방법이다.

첫 번째 코드는 간단히 재귀함수를 처음 배울 때 기본적으로 사용하는 팩토리얼 예제를 응용하면 된다.
식 자체는 문제에서 제시해 주었으니, 팩토리얼만 구현하여 식을 적용하면 된다. 
이때 중요한 점은, JS는 기본적으로 숫자 타입이 배정밀도 64비트 부동소수점 형식을 따른다(참고). 그렇기 때문에 나눗셈 연산을 하다 보면 컴퓨터 연산과정 내에서 소수점을 10진수에서 2진수로 변환하는 과정에 오차가 발생할 수 있다.(무한 소수를 담기 위해 유한 소수로 변환할 때 피치 못하게 값의 변동이 생기게 된다.) 따라서, 소수점의 연산을 할 때 이런 점을 조심해야 한다.
이 문제를 해결하기 위해서는 toFixed()나 Math.round()로 소수점을 정리해 줄 필요가 있고, 나는 Math.round()를 사용해 이것을 해결해 주었다.

두 번째 코드는 이항계수를 삼각형 모양으로 정리한 파스칼의 삼각형을 이용해 풀이하였다. n개의 공 중, r개를 고르는 것은 조합 nCr과 같기 때문에 nCr = n-1Cr-1 + n-1Cr 이를 활용한 문제 풀이를 해보았다.
우선 구한 조합의 값을 저장해 줄 이차원 배열을 만들어주었다. 그다음 조합을 구할 Combi()라는 함수를 만들어 주었다.
Combi()는 매개변수로 n과 r을 넣어 n개 중, r개를 뽑는 경우의 수를 구할 수 있는 함수이다.
여기서는 balls와 share를 넣어주었다.
기본적으로는 nCr = n-1Cr-1 + n-1Cr 이기 때문에 return (dy[balls][share] = Combi(balls - 1, share - 1) + Combi(balls - 1, share))로 n-1Cr-1과 n-1Cr를 더한 값을 반환해 주었다.
이 과정에서 dy에 이 값이 이미 저장되어 있다면 더 이상 재귀를 반복하지 않고, 해당 값을 사용할 수 있도록 메모이제이션을 해주었다.
종료 조건으로는 1C1일 경우나 nC0일 경우는 무조건 1이므로 1을 반환해 주어 재귀를 종료시켜 주었다.
만들어 둔 Combi() 함수에 매개변수로 받은 값을 넣어 구해주면 된다.

 

🕵️‍♂️ 코드

function solution(balls, share) {

  const fact = num => !num ? 1 : num * fact(num - 1);

  return Math.round(fact(balls) / fact(balls - share) / fact(share));

}

 

 

function solution(balls, share) {

  const dy = [...new Array(31)].map(() => Array(31).fill(0));

  const Combi = (balls, share) => {

    if (dy[balls][share]) return dy[balls][share];

    if (balls === share || !share) return 1;

    return (dy[balls][share] = Combi(balls - 1, share - 1) + Combi(balls - 1, share))

  }

  return Combi(balls, share);

}

 

---

📝 [Lv0] 중복된 숫자 개수

👀 문제 설명

정수가 담긴 배열 array와 정수 n이 매개변수로 주어질 때, array에 n이 몇 개 있는 지를 return 하도록 solution 함수를 완성해보세요.

 

🚨 제한 사항

• 1 ≤ array의 길이 ≤ 100
• 0 ≤ array의 원소 ≤ 1,000
• 0 ≤ n ≤ 1,000

 

💻 입출력 예

array	n	result
[1, 1, 2, 3, 4, 5]	1	2
[0, 2, 3, 4]	1	0

 

✨ 풀이 설명

filter()를 사용해서 array의 각 숫자가 n과 같은 것만 뽑아 새로운 배열로 만들었다. 이 배열의 길이를 구하면 n의 개수를 알 수 있다.

 

🕵️‍♂️ 코드

function solution(array, n) {

  return array.filter(item => item === n).length;

}

 

---

📝 [Lv0] 배열의 평균값

👀 문제 설명

정수 배열 numbers가 매개변수로 주어집니다. numbers의 원소의 평균값을 return하도록 solution 함수를 완성해주세요.

 

🚨 제한 사항

• 0 ≤ numbers의 원소 ≤ 1,000
• 1 ≤ numbers의 길이 ≤ 100
• 정답의 소수 부분이 .0 또는 .5인 경우만 입력으로 주어집니다.

 

💻 입출력 예

numbers	result
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]	5.5
[89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99]	94.0

 

✨ 풀이 설명

reduce()를 사용해 numbers의 모든 값을 더해주었다. 반환된 총합을 numbers의 길이, 즉 원소의 개수로 나눈 수를 반환해 주었다.

 

🕵️‍♂️ 코드

function solution(numbers) {

  return numbers.reduce((sum, num) => sum + num, 0) / numbers.length;

}

 

---

📝 [Lv0] 진료 순서 정하기

👀 문제 설명

외과의사 머쓱이는 응급실에 온 환자의 응급도를 기준으로 진료 순서를 정하려고 합니다. 정수 배열 emergency가 매개변수로 주어질 때 응급도가 높은 순서대로 진료 순서를 정한 배열을 return하도록 solution 함수를 완성해주세요.

 

🚨 제한 사항

• 중복된 원소는 없습니다.
• 1 ≤ emergency의 길이 ≤ 10
• 1 ≤ emergency의 원소 ≤ 100

 

💻 입출력 예

emergency	result
[3, 76, 24]	[3, 1, 2]
[1, 2, 3, 4, 5, 6, 7]	[7, 6, 5, 4, 3, 2, 1]
[30, 10, 23, 6, 100]	[2, 4, 3, 5, 1]

 

✨ 풀이 설명

등수 매기기 문제와 비슷한 문제이다. 다른 점이라면 평균을 구하지 않고 그냥 emergency 안의 수가 큰 순서대로 정렬하면 된다는 점.

배열의 길이가 길지 않아 그냥 이중 반복으로 해결하였다. 만약 길이가 더 길다면 이전에 풀었던 방식으로 푸는 것이 시간 효율에서는 더 좋을 것이다.

 

🕵️‍♂️ 코드

function solution(emergency) {

  return emergency.map(pat => emergency.filter(other => other > pat).length + 1);

}

 

---

📝 [Lv0] 팩토리얼

👀 문제 설명

i팩토리얼 (i!)은 1부터 i까지 정수의 곱을 의미합니다. 예를들어 5! = 5 * 4 * 3 * 2 * 1 = 120 입니다. 정수 n이 주어질 때 다음 조건을 만족하는 가장 큰 정수 i를 return 하도록 solution 함수를 완성해주세요.

• i! ≤ n

 

🚨 제한 사항

• 0 < n ≤ 3,628,800

 

💻 입출력 예

n	result
3628800	10
7	3

 

✨ 풀이 설명

팩토리얼 공식처럼 해당 값이 n보다 커질 때까지 1부터 차례대로 값을 곱해주었다. while문이 종료되면 해당 수가 n보다 크다는 뜻이므로 n보다 같거나 작은 가장 큰 수를 만족하는 수는 i - 1이 된다.

 

🕵️‍♂️ 코드

function solution(n) {

  let i = 1, mul = 1;

  while (n >= mul) mul *= ++i;

  return i - 1;

}