소수 만들기

문제 설명

주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요.

제한사항

• nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다.
• nums의 각 원소는 1 이상 1,000 이하의 자연수이며, 중복된 숫자가 들어있지 않습니다.

입출력 예

nums	result
[1,2,3,4]	1
[1,2,7,6,4]	4

처음 생각

처음에는 문제를 보자마자 아 조합문제니까 재귀를 이용해서 풀어야겠다!하고 시작했다. 답은 맞았는데 1점 밖에 안주는걸 보고 응?하고 다른 사람의 풀이를 봤는데,
for문으로만 푸신 분들이 많았다.. 그래서 꼭 재귀가 답은 아니구나 라는 생각이 다시한번 들었다.
만약, 뽑아야 하는 수가 더 많았으면 재귀를 활용해서 할 수 밖에 없겠지만, 3가지 숫자이기 때문에 for문을 중첩으로해서 충분히 가능한 문제였다.

문제풀이

3가지 숫자를 골라서 더해야 하기 때문에 for문을 3개 사용하면 된다. 2번째 포문은 1번째 포문보다 +1에서 시작하고, 3번째 포문은 2번째 포문보다 +1에서 시작하게 만들어서 모든 숫자를 보면 된다. 그리고 total값이 소수일 때만 answer++한다. (여기서 answer값은 0으로 초기화 => 0인 경우가 존재.)

function solution(nums) {
  var answer = 0;
  // answer = permutation(nums,0,1);
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      for (let k = j + 1; k < nums.length; k++) {
        let total = nums[i] + nums[j] + nums[k];
        if (checkPrime(total)) {
          answer++;
        }
      }
    }
  }

  return answer;
}

function checkPrime(num) {
  for (let i = 2; i <= Math.sqrt(num); i++) {
    if (num % i === 0) return false;
  }
  return true;
}

추가, 재귀로 순열을 짜서 품.

function solution(nums) {
  var answer = 0;
  answer = permutation(nums, 0, 1);
  return answer;
}

function permutation(nums, total, dep) {
  return nums.reduce((acc, val, idx) => {
    let newArr = [...nums];
    if (idx === 0) newArr.splice(idx, 1);
    else newArr.splice(0, idx + 1);
    total += val;
    dep++;
    if (dep === 3) {
      if (checkPrime(total)) return ++acc;
      else return acc;
    }
    let result = permutation(nums, total, dep);
    acc += result;
    total -= val;
    return acc;
  }, 0);
}

function checkPrime(num) {
  for (let i = 2; i <= Math.sqrt(num); i++) {
    if (num % i === 0) return false;
  }
  return true;
}