Level 1 ) 소수 만들기

문제 설명

주어진 숫자 중 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
[1,2,4]를 이용해서 7을 만들 수 있습니다.

입출력 예 #2
[1,2,4]를 이용해서 7을 만들 수 있습니다.
[1,4,6]을 이용해서 11을 만들 수 있습니다.
[2,4,7]을 이용해서 13을 만들 수 있습니다.
[4,6,7]을 이용해서 17을 만들 수 있습니다.

아이디어

가장 직관적인 방법은 반복문을 이용해 3개씩 다 더해보면서 소수를 판별하는 것인데, 좀 더 효율적인 방법은 없을지 생각해보았다.

3개를 더해서 소수가 되려면 어떤 조건이 필요할까 생각해봤을 때, 짝수는 2 외에 무조건 소수가 될 수 없으니 제외하고 홀수가 되는 경우만 고려해 소수를 판별해보는 방법이 떠올랐다.

3개를 더해서 홀수가 되려면, 크게 두 가지 케이스가 있다.
1. 홀수 + 홀수 + 홀수
2. 짝수 + 짝수 + 홀수

이를 위해 주어진 수를 홀수/짝수로 분류해서 더하고 소수를 판별하는 방식을 생각해봤는데, 짝수/홀수를 분류해 배열에 저장하는 과정에서 공간 복잡도가 늘어나고 두 가지 케이스를 나누어 더하는 과정에서 삼중 반복문을 써야 하는게 동일하기 때문에 시간 복잡도도 크게 개선되지 않는다고 판단했다.

풀이

1. 소수 판별 함수를 따로 만들기
2. 삼중 반복문을 이용해 3개씩 더하면서 소수 판별을 해 소수의 갯수를 구한다.

function solution(nums) {
    let answer = 0;
    function isPrime(val){
        for(let i=2;i<val;i++){
            if(val%i === 0) return false;
        }
        return true;
    }
    for(let i=0;i<nums.length-2;i++){
        for(let j=i+1;j<nums.length-1;j++){
            for(let k=j+1;k<nums.length;k++){
                if(isPrime(nums[i] + nums[j] + nums[k])) answer++;
            }
        }
    }
    return answer;
}

개선

어떤 수의 약수는 중간값을 기준으로 대칭성을 보이기 때문에, 소수 판별에 있어 모든 수로 나눠보지 않고 제곱근까지만 나눠도 소수인지 알 수 있다.
(Math.sqrt( ) 이용)

function solution(nums) {
    let answer = 0;
    function isPrime(val){
        for(let i=2;i<Math.sqrt(val);i++){
            if(val%i === 0) return false;
        }
        return true;
    }
    for(let i=0;i<nums.length-2;i++){
        for(let j=i+1;j<nums.length-1;j++){
            for(let k=j+1;k<nums.length;k++){
                if(isPrime(nums[i] + nums[j] + nums[k])) answer++;
            }
        }
    }
    return answer;
}