JS알고리즘 | 프로그래머스(Level 1) - 소수만들기

완전탐색으로 해결해야하는 문제 -> 조합을 이용

 

4Combination3 = 4C3

4개 중에 3개씩 선택할 때 나올 수 있는 모든 조합을 구한다. 이 때, 조합의 순서는 상관이 없다. 순서가 바뀌어도 같은 구성이기 때문에 하나의 조합으로 취급한다. 

 

소수 

: 1과 자기 자신만을 약수로 갖는 수, 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수

 

처음 시도한 방법

조합으로 모든 경우의 수 배열로 찾아서 다 더한다음에 소수판별할 생각이었다. -> 실패

 

조합을 이용하기

서로 다른 n개의 물건에서 순서를 생각하지않고 r개를 택할 때, n개에서 r를 택하는 조합 -> nCr

5개 중에서 3개를 더하는 조합 5C3 = 5*4*3 /3*2*1 = 10가지

 

배열의 처음부터 하나씩 고정하면서 뒤의 나머지 배열에 대해서 조합을 구한다. 

 

 

 

코드

const solution = (nums) => {
  let answer = 0;
  const len = nums.length;

  for (let i = 0; i < len; i++) {
    for (let j = i + 1; j < len; j++) {
      for (let k = j + 1; k < len; k++) {
        const sum = nums[i] + nums[j] + nums[k];
        if (isPrime(sum)) answer++;
      }
    }
  }
  return answer;
}

const isPrime = (sum) => {
  for (let i = 2; i < sum; i++)
    if (sum % i === 0) return false;
  return true;
}