[코드테스트] 소수만들기

소수 만들기

문제

주어진 숫자 중 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. 3개의 반복되지 않는 수를 골라 3가지 수를 더한다.
2. 더한 3가지 수가 약수인지 아닌지 판정한다.
3. 약수이면 갯수 cnt에 더한다.

나의 풀이의 단점은 3가지 수를 담는데 사용한 배열공간, 매개변수로 받아온 값들이 이룰 수 있는 조합된 3가지 수들의 배열 공간, 이 3가지 수를 더한 값들을 담는데 사용한 배열공간, 매개변수를 담기위한 배열공간 등 원하는 결과에 비해 비효율적인 공간낭비가 많다.

하지만 소수를 구하는 공식을 배웠다는 점.
에라토스테네스의 체 참고하기
반복되지 않는 배열의 수를 골라 담을 수 있는 것을 배웠다는 점.
위 2가지 사항에 의미를 두고 테스트를 진행하였다.

//3가지 수를 골라 담을 배열 공간을 만들었다. 
let arr = [];
//3가지 수의 배열들을 담을 배열 공간을 만들었다.
let all = [];
//3가지 수의 합들을 담는 배열공간을 만들었다.
let result= [];
//소수가 아닌 수를 카운트하기 위해 cnt를 만들었다. 
let cnt = 0;
let num = [];
function solution(num){
//num의 배열길이를 모르니 num.lenght만큼 반복하였다.
    for(let i =0; i < num.length; i++){
        for(let j = i+1; j<num.length; j++){
//최초 값이 들어간 자리를 반복하지 않기위해 j는 i+1부터 시작했다.
            for(let k = j+1; k<num.length; k++){
//다음 k값은 j를 반복하지 않기 위해 j+1부터 시작했다.
                arr.push(num[i]); 
                arr.push(num[j]);
                arr.push(num[k]);
//arr에는 i,j,k로부터 값을 받아 3개의 값이 들어간다. 
//arr이 여러개이니 이 여러 배열을 담을 저장공간을 만든다. 
                all.push(arr)
//arr를 초기화 시켜서 all이라는 배열에 값들을 축척시킨다. 
                arr = [];
            }
        }
    }
    console.log(all)
    for(let i = 0; i < all.length; i++){
//all에 들어있는 3가지 수들의 배열들을 reduce시켜 result에 담았다. 
    result[i] = all[i].reduce((sum, val)=> (sum+val),0) 
    }
    console.log(result)

// 이제 result에는 매개변수에서 가져온 값들의 세가지 수들의 합 배열이 담겨있다. 
// result 의 길이 만큼 i를 반복시키고 j를 만들어 2보다 크고 result[i]보다 작은 수로 나누어 그 수가 나누어 떨어질때 소수가 아님으로 0을 넣는다. 
    for(let i = 0; i < result.length; i++){
        for(let j = 2; j < result[i]; j++){
            if(result[i] % j === 0){
                result[i] = 0;
                continue;
            }   
        }
    }
//이제 result에는 소수를 제외한 나머지 수들은 0이 담겨있다. 
//0보다 큰 수의 갯수가 소수의 갯수가 된다!!! 
//소수가 아닌 수의 갯수를 카운트 하기위해 cnt를 만들자 
    for(let i = 0; i < result.length; i++){
//result[i] value가 0이상이면 cnt를 증가시킨다. 
        if(result[i]>0){
            cnt++
        }
    }
//cnt를 return 시킨다. 
    return cnt;
}
//함수를 실행시킨다. 
solution(num)

다른 사람 풀이

function primecheck(n){
    for(var i=2;i<=Math.sqrt(n);i++){
        if(n%i == 0){
            return false;
        }
    }
    return true;    
}
function solution(nums){
    var cnt = 0;
    for(var i=0;i<nums.length-2;i++){
        for(var j=i+1;j<nums.length-1;j++){
            for(var w=j+1;w<nums.length;w++){
                    //console.log(nums[i]+"/"+nums[j]+"/"+nums[w]);

                    if(primecheck(nums[i]+nums[j]+nums[w])){
                        //console.log(nums[i]+nums[j]+nums[w]);
                        cnt++;
                    }
            }
        }
    }
    return cnt;
}

좋은 웹페이지 즐겨찾기