볼링공 고르기

👉 문제

A와 B 두 사람이 볼링을 치고 있는데, 두 사람은 서로 무게가 다른 볼링공을 고르려고 한다.

볼링공은 총 N개 있으며, 공의 번호는 1번부터 순서대로 부여된다.

같은 무게의 공이 여러개 있을 수 있지만, 서로 다른 공으로 간주한다.

condition: 1 <= N <= 1000, 1 <= M <= 10

output: 두 사람이 볼링공을 고르는 경우의 수

 

👉 내 코드

간단한 문제이지만 생각 없이 이중 반복문을 사용해서 답을 구했다.

결과적으로 답은 도출되었지만 효율적으로 많이 떨어지는 코드이다.

const N=8, M=5; // N은 공의 개수, M은 볼링 공의 최대 무게
const arr = [1,5,4,3,2,4,5,2]; // 볼링공의 무게

let result = 0;
for(let i=0 ; i<arr.length ; i++) {
   for(let j=i+1 ; j<arr.length ; j++) {
     if(arr[i] !== arr[j])  result += 1;
   }
}
console.log('output: ', result);

 

👉 답안 코드

공이 무게별로 몇 개가 있는지를 구한다.

아래 예시의 경우 1번 공은 1개, 2번 공은 2개, 3번 공은 3개가 있다.

 

1번 공은 2번 공 2개와 3번 공 3개와 모두 조합이 가능하다.

2번 공은 3번 공 3개와 조합이 가능하다.

3번 공은 매치할수 있는 조합이 없다.

 

그래서 정답은 1번개수*(2번개수 + 3번개수) + 2번개수*(3번개수) 가 된다.

 

이 과정을 자바스크립트로 나타내면 아래와 같다.

const N=5, M=3;
const arr = [1, 3, 2, 3, 2];

let result = 0;

// 특정 index부터 배열의 합계를 구하는 함수
function sum(ball, index) {
  let sum = 0;
  for(let i=index ; i<ball.length ; i++) {
    sum += ball[i];
  }
  return sum;
}

const balls = Array.from({length: M+1}, () => 0);
for(n of arr)  balls[n]++;

for(let i=1 ; i<M ; i++) {
  result += balls[i] * sum(balls, i+1);
}

console.log('output: ', result);