Algorithm problem-조합

1. 문제

• 중복되지 않는 숫자로 이루어진 카드를 여러 장 받고
• 그 카드 중 3장씩을 골라 그 합이 소수가 되는 경우의 수를 리턴

2. 시도

• 소수를 판별하는 함수를 작성
• 조합을 만들어줄 함수 작성
• 소수의 갯수를 세어줄 카운터 선언
• 3부분집합을 만들어 그 숫자를 모두 더하고
• 더한 숫자가 소수인지를 판별, 맞으면 카운팅
• 전부 다 계산하고, 카운팅 리턴하는 코드를 짜보려고 하였음

3. 수도코드

// 너무 복잡하게 짜여서 레퍼런스를 참조할 것
function isPrime(num) {
  if (num === 2) return true;
  for (let i = 2; i <= Math.floor(Math.sqrt(num)); i++) {
    if (num % i === 0) return false;
  }
  return true;
}
function getCombinations(array, selectNumber) {
    const results = [];
    if(selectNumber === 1){
        return array.map((element) => [element]);
    }
    array.forEach((fixed, index, origin) => {
        const rest = origin.slice(index+1);
        const combinations = getCombinations(rest, selectNumber - 1);
        const attached = combinations.map((combination) => [fixed, ...combination]);
        results.push(...attached);
    });
    return results;
}
function boringBlackjack(cards) {
  let cnt = 0;
  let result = getCombinations(cards, 3);
  let sum = [];
  for (let i = 0; i < result.length; i++) {
    let a = 0;
    for (let j = 0; j < result[i].length; j++) {
      a = a + result[i][j]
    }
    sum.push(a)
  }
  for (let k = 0; k < sum.length; k++) {
    if (isPrime(sum[k])) {
      cnt++
    }
  }
  return cnt;
}

4. 레퍼런스

function boringBlackjack(cards) {
  let count = 0;

    // 1. cards 에서 카드 3장 뽑기
    let length = cards.length;
    // 카드 뽑는 방식은 첫 카드를 cards 의 0번 index 부터 고정해 놓고 1씩 뒤로 옮겨간다
    for (let i = 0; i < length; i++) {
    // 두 번째 카드의 인덱스는 첫 카드 + 1에서 시작해야 하고
      for (let j = i + 1; j < length; j++) {
    // 세 번째 카드의 인덱스는 두 번째 카드 + 1에서 시작해야 한다 
        for (let k = j + 1; k < length; k++) {
          const number = cards[i] + cards[j] + cards[k];
          // 세 카드의 합이 소수이면 경우의 수 + 1
          if (isPrime(number)) count++;
        }
      }
    }
  
    //2. 소수 판별
    function isPrime(number) {
    // 2부터 비교하기 시작해서 나누어 떨어지는 수가 있으면 소수가 아니다
    // for 문 조건을 number/2 로 해도 되는 이유는 i > number/2 가 되면 몫이 절대 0이 될수 없기 때문에
    // number/2 까지만 비교해 보아도 소수 판별이 가능하다
      for (let i = 2; i < number/2; i++) {
        if (number % i === 0) return false;
      }
      return true;
    }
  
    return count;
}