[알고리즘] 소수 구하기 -프로그래머스 코딩테스트 연습 by JavaScript

이 문제는 숫자들이 들어가 있는 배열이 주어지는데, 거기서 3개의 숫자를 골라 더한 후, 그 숫자가 소수인지 아닌지 판별하여 그러한 수가 총 몇개 있는지 구하는 문제이다.

이 문제의 해결법은 보자마자 대략적인 생각이 났고 실행에 옮겼다. 내가 생각한 방법은 조합을 구하는 방식을 이용하는 것이다. 주어진 배열에서 3개씩 뽑아 더한 후 하나의 배열에 모두 저장한다. 그리고 그 배열을 돌면서 소수인지 아닌지 판별한 후 answer를 리턴해 준다. 소수를 구하는 방식은 2부터 해당 수의 제곱근까지 나눠주어 소수인지 아닌지 판별하는 방식을 이용하였다. 그리고 조합의 구현은 스스로 구현해 보려했으나 생각보다 잘 되지 않아 결국 한 블로그를 참고하였다.

문제풀이
function solution(nums) {
    var answer = 0;
    
    let threeNums = [];
    let arr = getCombinations(nums, 3);
    
    for(let i=0; i<arr.length;i++){
        threeNums.push(arr[i][0]+arr[i][1]+arr[i][2])
    }
    
    for(let i=0; i<threeNums.length;i++){
        if(isPrime(threeNums[i])){
            answer++;
            // console.log(threeNums[i])
        }
    }
    
    return answer;
}

const getCombinations = function (arr, selectNumber) {
  const results = [];
  if (selectNumber === 1) return arr.map((value) => [value]);

  arr.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 isPrime(prime){
    for(let i=2; i<=Math.sqrt(prime);i++){
        // console.log(`[${prime}] : ${i}`)
        if(prime%i === 0){
            return false;
        }
    }
    return true;
}