[Algorithm] 프로그래머스 - 소수 만들기 (Javascript)

풀이

1. nums의 배열값을 3개씩 조합해서 새로운 배열로 저장한다. (조합 알고리즘)

   조합 알고리즘
   1. 재귀함수로 구현한다.
   2. 조합할 갯수를 인자로 받는데 , 만약 조합할 갯수가 1개이면 인자로 받은 배열을 2차원 배열로만 바꿔서 return한다.
   3. arr을 순회하며 인덱스 하나를 고정하고 뒤에 붙는 인덱스를 조합한다.

2. 조합한 배열을 순회하며 합을 구한 배열을 구한다.
3. 합의 배열을 순회하며 소수이면 answer++을 해준다. (소수 판별 알고리즘)

   소수 판별 알고리즘
   1. 숫자가 2면 소수이기 때문에 return true
   2. 숫자의 제곱근으로 나눠서 0이면 소수가 아니므로 return false
   3. 그게 아니라면 소수이기때문에 return true

4. answer를 return한다.

코드

function solution(nums) {
    let answer = 0;
    const nums3Combinations = getCombinations(nums,3);
    const comSums = getSums(nums3Combinations);
    comSums.forEach(v=> isPrime(v) ? answer++ : null)
    return answer
}

const getCombinations = (arr,selectNum) => {
    if(selectNum === 1) return arr.map(v=>[v])

    const result = [];

    arr.forEach((v,index,origin)=>{
        const rest = origin.slice(index+1);
        const combinations = getCombinations(rest,selectNum-1);
        const attached = combinations.map(com=>[v,...com]);
        result.push(...attached)
    })
    return result
}

const getSums = (arr) => {
    const sums = [];
    
    for(let i=0;i<arr.length;i++){
        const sum = arr[i].reduce((acc,curr)=>acc+curr,0);
        sums.push(sum)
    }
    return sums.sort((a,b)=>a-b);
};

const 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
}

참고
- JS 순열과 조합
- JS 소수판별식