프로그래머스 소수 만들기

링크 : https://school.programmers.co.kr/learn/courses/30/lessons/12977

문제 풀이

nums에서 3개의 수를 더한 값이 소수인지 판단하는 문제로

1. dfs를 이용해 3개를 선택하는 로직을 작성 -> depth가 3인 경우 3개의 숫자가 선택된 것

2. sum은 3개의 숫자를 선택하여 더한 값으로 isPrime함수를 통해 소수인지 판단, 이후 더이상 진행하지 못하도록 return

3. isPrime함수는 홀수인 경우 아래와 같은 로직을 통해 소수를 검사

for (let i = 3; i <= Math.sqrt(number); i += 2) {
    if (number % i === 0) return false;
}

소수를 구하기위해 검사할 값(number)의 루트 값 까지 계산하면 됨, 또한 짝수로 검사하는건 의미가 없으므로 홀수만 검사되도록 + 2씩 증가

---

function solution(nums) {
    var answer = 0;
    
    function isPrime(number) {
        if (number % 2 === 0) return false;
        for (let i = 3; i <= Math.sqrt(number); i += 2) {
            if (number % i === 0) return false;
        }
        
        return true;
    }
    
    function dfs(index, sum, depth) {
        if (depth === 3) {
            if (isPrime(sum)) answer++;
            return;
        }
        
        for (let i = index; i < nums.length; i++) {
            dfs(i + 1, sum + nums[i], depth + 1);
        }
    }
    
    dfs(0, 0, 0);
    return answer;
}

---

결론

소수판별하는 로직에 '에라토스테네스의 체'라는 것을 이용하면 더 효율적으로 검사가능한데 이 문제에서는 굳이 필요 없음