Level2. 프로그래머스 소수 만들기- JavaScript

 

접근

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

 

숫자 3개를 더해 그게 소수인지 판별하는 문제이다.

그래서 전체적인 흐름은 배열안에 숫자 3개를 더하고 이게 에라토스테네스의 체에서 소수인지 확인 하면 끝이다.

 

더 자세히 짚어보면 

[1,2,3,4]가 있을 때 1,2,3 / 2,1,3 / 3,1,2는 서로 다른 순서이지만 결국 이들을 합하게 되면 모두 같은 6이므로 순서를 신경쓰며 조합을 만들 필요는 없다. 따라서 [1,2,3,4]로 만들 수 있는 조합의 개수는 1,2,3 / 1,3,4 / 1,2,4 / 2,3,4 가 된다.   

그리고 에라토스테네스의 체를 만든다.
문제에서 각 원소는 1이상 1000이하이다. 이 원소 3개를 뽑았을 때 각각 최대값을 뽑았다고 할때 1000+999+998인데 대략 3000으로 잡고 에라토스테네스의 체의 최댓값은 3000으로 잡는다. 

마지막으로 각 조합의 합이 들어 있는 배열을 순회하면서 소수 인지 검증하고 소수인 개수를 출력하면 된다.

 

코드

function solution(nums) {
    var answer = -1;
    let sumArr = [];
    //에라토스테네스에서 2~3000까지의 수 중에서 소수를 나타내는 배열을 만든다.
    let prime = makePrimeNum(3000);
    
    //뽑아야 하는 3자리 중에 첫번째 자리 고정
    // 고정할때 해당 index뒤에 2개를 더 붙일 수 있는지 확인
    for(let i=0; i<=nums.length-3; i++){
        // 두번째 자리 고정 뒤에 1개를 더 붙일 수 있는지 확인
        for(let j=i+1; j<=nums.length-2; j++){
            for(let k=j+1; k<nums.length; k++){
                sumArr.push(nums[i]+nums[j]+nums[k]);
            }
        }
    }
    // 소수인 배열을 만들고 그 배열의 개수를 answer에 대입
    answer = sumArr.filter(n => prime[n] != false).length;
    return answer;
}

function makePrimeNum(length){
    let arr = [];
    // 0,1은 소수가 아니므로 2부터 진행
    for(let i=2; i<=length; i++){
        if(arr[i] == false) continue;
        // 자기 자신을 제외한 배수를 제거해야 하기 때문에 i+i부터 진행
        for(let k=i+i; k<=length; k+=i){
            arr[k] = false;
        }
    }
    return arr;
}