[JS] 프로그래머스 - 삼총사 (조합 풀이과정)

📣  문제 풀이에 앞서 JS로 조합을 구현하는 과정을 알아보자.

✔️ 조합 : 서로 다른 n개의 물건에서 순서를 생각하지 않고 r개를 택하는 것 => nCr

✔️ 구현 과정 : 배열의 처음 요소부터 하나씩 고정하고, 고정된 요소를 제외한 요소들 중에서 r-1개를 조합해서 붙이는 방법

✔️ 재귀적으로 푸는 게 좋다-> 조합을 구하는 과정은 계속 반복되기 때문에!

 

📌 문제

한국중학교에 다니는 학생들은 각자 정수 번호를 갖고 있습니다. 이 학교 학생 3명의 정수 번호를 더했을 때 0이 되면 3명의 학생은 삼총사라고 합니다. 예를 들어, 5명의 학생이 있고, 각각의 정수 번호가 순서대로 -2, 3, 0, 2, -5일 때, 첫 번째, 세 번째, 네 번째 학생의 정수 번호를 더하면 0이므로 세 학생은 삼총사입니다. 또한, 두 번째, 네 번째, 다섯 번째 학생의 정수 번호를 더해도 0이므로 세 학생도 삼총사입니다. 따라서 이 경우 한국중학교에서는 두 가지 방법으로 삼총사를 만들 수 있습니다.

한국중학교 학생들의 번호를 나타내는 정수 배열 number가 매개변수로 주어질 때, 학생들 중 삼총사를 만들 수 있는 방법의 수를 return 하도록 solution 함수를 완성하세요.

 

✏️ 풀이

function solution(number) {
  let noOverlap = [];
  let result = 0;
  
  for(let i=0; i<number.length; i++){
      if(noOverlap.includes(number[i]) === false){
          noOverlap.push(number[i]);
      }
  }
  
  let combinations = getCombinations(number, 3);
  
  for(let i=0; i<combinations.length; i++){
    let sum = 0;
    for(let j=0; j<combinations[i].length; j++){
        sum += combinations[i][j];
    }
    if(sum === 0){
      result++;
    }
  }
  return result;
}

const getCombinations = function (n, r) {
  const results = [];
  if (r === 1){
    return n.map((el) => [el]); 
  }

  n.forEach((fixed, index, origin) => {
    const rest = origin.slice(index + 1); 
    const combinations = getCombinations(rest, r - 1); 
    const attached = combinations.map((el) => [fixed, ...el]); 
    results.push(...attached); 
  });

  return results; 
}

➰ 반복되는 수는 없어야 하니까 일단 받은 배열에서 중복되는 숫자 제거해서 noOverlap 배열 만들어주기.

➰ noOverlap 배열을 getCombinations() 함수 인자로 줘서 3개 조합 구하기.

➰ 구한 조합에서 각각 배열 요소 더했을 때 0 이되면 최종 답인 result ++ 해주기.