[ 08.10 ] 조합

🃏 문제

평범한 블랙잭 게임에서 수시로 패배하자 흥미가 떨어진 김코딩은 박타짜에게 게임룰을 변형하여 새로운 카드 놀이를 해 볼 것을 제안합니다.
새로운 룰은 다음과 같습니다.
1. 숫자로 이루어진 카드를 여러 장 받습니다.
2. 3장씩 카드를 고르고, 3장에 적힌 숫자들의 합이 소수인지 확인합니다.
3. 받아든 카드로 만들 수 있는 소수의 개수가 많은 사람이 이기게 됩니다.
예로, [1, 2, 3, 4]라는 카드를 받았을 때 만들 수 있는 숫자는 6, 7, 8, 9이고, 소수는 7 하나이기 때문에 가지고 있는 소수의 개수는 1개입니다.
[2, 3, 4, 8, 13]라는 카드를 받았을 때 만들 수 있는 숫자는 9, 13, 18, 14, 19, 23, 15, 20, 24, 25이고, 소수는 13, 19, 23 총 3개이기 때문에 가지고 있는 소수의 개수는 3개입니다.
게임을 진행하기 전에 소수에 대해 아무런 지식이 없는 박타짜는 게임을 며칠 미룬 뒤, 게임의 룰을 따르는 함수를 만들기로 했습니다.
소수에 약한 박타짜를 도와 여러 장의 카드 중 세 장씩 조합해 소수가 되는 경우의 수를 리턴하는 함수를 완성해 주세요.

🃏 입력

인자 1
cards: Array 3개 이상 50개 이하의 카드가 숫자로 들어 있는 배열
출력
Number 타입을 리턴해야 합니다.

🃏 주의사항

cards 에는 중복된 숫자의 카드는 들어있지 않습니다.
각 카드에 적힌 수는 1이상 1,000이하의 자연수입니다.

🃏 입출력 예시

let output = boringBlackjack([1, 2, 3, 4]);
console.log(output); // 1
let output = boringBlackjack([2, 3, 4, 8, 13]);
console.log(output); // 3

🃏 문제에 대한 이해

cards 라는 배열에 임의의 숫자로 나열된 카드들이 있는데 여기서 총 세장의 카드를 골라야 한다고 명시되어있다. 세개정도니까 3중포문을 사용해도 좋을것 같다. (재귀 어려브 .. )
뽑은 세장의 합이 소수일때, 그 갯수를 구하는 문제이다.
입출력 예시를 보니 한번 뽑았던 숫자를 연속해서 뽑을 수 없으며 나온 숫자의 합이 같으면 안된다.
(1,1,1 이렇게 뽑을수없고(중복순열), 1,2,3 과 1,3,2(순열)의 합은 어쨌든 같으므로 제외시킨다.)
즉, 이문제는 조합문제라고 볼수있다.

🃏 수도코드

1. 연속하여 같은수를 더하면 안되므로 3중포문을 돌릴 시 이전의 for문변수에 +1 을 해주어 돌려준다. 만약 중복순열이었다면 let i =0, let j = 0, let k = 0; 이런식으로 했겠지.
2. i,j,k 의 요소를 다 더한 값을 한 배열에 일단 다 푸쉬해준다.
3. 푸시된 배열요소들 중에서 소수인 아이들만 판별하여 나타낸다.
4. 소수판별 함수를 생성한다. => 템플릿으로 외워두기
5. 소수는 짝수, 홀수중에서도 제곱근이가능한 수는 return false.
6. 2부터 매개변수로 받은 수를 2로 나눈값까지 for 문을 돌려서 그 수를 i로 나눴을때 0이 되면 false, 아니라면 전부 트루로 바꿔준다.
   (여기서 매개변수로 받은 숫자를 2로 나누는 이유는 i > number/2 가 되면 몫이 절대 0이 될수 없기 때문에 number/2 까지만 비교해 보아도 소수 판별이 가능하기 때문이다.)
   뭐 그렇다고 한다. 수학 빠가사리라 그냥 외워버림.
7. 만든 소수함수를 3중 for 문에 대입시켜준다.
   => 여기서 또 공포의 필터링이 나옴.

🃏 풀이

function boringBlackjack(cards) {
  // TODO: 여기에 코드를 작성합니다.
  // cards = [2, 3, 4, 8, 13] ;
  // cards 에서 세가지수를 더해서 나올수 있는 모든 경우의수 
  // 단, 같은수끼리 더하면 안된다. 그리고 순서가 바뀌어도 어차피 값은 같기 때문에 
  // (조합) 으로 풀어야 한다.
  const isPrime = (num) => {
    for(let i = 2; i<num/2; i++){
      if(num % i === 0) return false;
    }
    return true;
  }

  //let count = 0;
  let arr = []
  for(let i = 0; i<cards.length; i++){
    for(let j = i+1; j<cards.length; j++){
      for(let k = j+1; k<cards.length;k++){
        let add = cards[i] + cards[j] + cards[k];
        arr.push(add); //[9, 13, 18, 14, 19, 23, 15, 20, 24, 25]
        arr = arr.filter((el)=>{
          if(isPrime(el)) return el;
        })
      }
    }
  }
  return arr.length;
}

나는 filter 를 이용해서 각 요소가 소수인것만 리턴한 값을 arr 에 재할당하고 그 arr의 길이를 최종리턴하는것으로 구했다.
하지만 굳이 새 배열에 담지 않고 isPrime() 함수안에 add 를 넣고 해당되는 요소가 있을때마다 count++ 를 했어도 되었다.

여튼 용썼다.

만약, 카드세장으로 정해진것이 아니라 임의의 값만큼 빼야하는 함수를 만들어야 한다면 어떻게 될까?

function boringBlackjack(cards) {
  // TODO: 여기에 코드를 작성합니다.

  // 소수판별
  const isPrime = (num) => {
    for(let i = 2; i<num/2; i++){
      if(num % i === 0) return false;
    }
    return true;
  }
  
  //조합
  const com = (array = cards, num, temp = []) => {
    if(num === 0){
      let check = temp.reduce((acc, cur) => acc + cur, 0);
      if(isPrime(check)){
        results.push(temp)
        return;
      }
    }
    array.forEach((el, idx, arr) => { // 
      newArr = arr.slice(idx+1);
      com(newArr, num-1, temp.concat(el));
    })
  }

  com();
  return results.length;
}

뭐 이정도가 될 수 있겠다.

*참고 - 이문제는 프로그래머스 1단계 소수만들기와 완.전.히 똑같다.
단, 내가 배열로 필터링해서 푼것 대신

let add = nums[i]+nums[j]+nums[k];
 if(isPrime(add)) count++;

이렇게 풀어야 정확도 100이 나옴.