소수만들기(dfs)

배열에서 3개의 수를 뽑아 더한 값이 '소수'인 경우를 찾는 문제이다.

for을 3번은 사용해야 해결이 가능할거 같은데 도저히 좋은 방법같지가 않다. 그래서 dfs로 해결했다.

function isPrime(num){
    for(let i = 2; i <= Math.sqrt(num); i++){
        if(num % i === 0){
            return false
        }
    }
    return true
}

function solution(nums) {
    var answer = [];
    
    const dfs = (nums, cnt, arr = []) => {
        if(cnt === 3) return answer.push(arr.reduce((a, c) => a + c));
        for(let i = 0; i < nums.length; i++){
            arr.push(nums[i]);
            dfs(nums.slice(i+1), cnt + 1, arr);
            arr.pop()
        }

    }
    dfs(nums, 0);
    return answer.filter(v => isPrime(v)).length;
}

먼저 소수를 판변하는 부분은 isPrime 함수로 따로 정의했다.
N의 약수는 무조건 sqrt(N)의 범위에 존재한다. 그래서 Math.sqrt를 사용했다.

소수 구하는 부분은 완성했으니 배열에서 3개를 뽑는 부분을 설계하자.
dfs라는 함수를 만들었다. 인자 3개를 받고 있다.

• dfs 함수 동작

1. dfs(nums, 0); 으로 nums배열과 0을 넣었다. 설명을 위해 nums는 [1, 2, 3, 4]라고 해보자.

2. for문 부터 보자. i=0이고, arr에 nums[i]를 push해주었다. 다시 dfs함수에 들어가면서 이제 [2, 3, 4] 에서 뽑아야 하므로, nums.slice(i+1)을 첫번째 인자에 넣었다. 그리고 카운트 하기 위해 cnt를 1증가시켰고, arr 배열을 그대로 넣어주었다.

3. 이제 dfs안에 들어왔다. cnt는 1이므로 if문에 들어가지 않는다. for문에 들어가 i=0 부터 다시 시작한다. 하지만 여기서 배열은 [2, 3, 4]라는 것을 명심하자. cnt가 3 전까지는 dfs함수에 또 들어갈 것이다.

4. 위 과정을 반복하다가 arr에 [1, 2, 3]이 push되었을 때, cnt가 3이 되어 if문 안에 들어간다. reduce로 1+2+3의 결과값 6을 반환하고 answer에 push 해준다. 이 값을 return으로 주었기 때문에 dfs를 탈출한다.
   dfs를 탈출한 직후, 현재 for문에서 i = 0 인 상태일 것이다. 그리고 arr에 [1, 2, 3]가 들어가 있고, nums는 [3, 4]이다. 이제 arr.pop()을 해주어 arr에 [1, 2]가 남고 i=1로 증가한다.
   [3, 4]에서 nums[i]에 해당하는 4를 arr에 push 한다.

dfs는 위와같이 동작하고 있다. 만약에 이 글이 이해가 안간다면 반복해서 읽어보다가 직접 동작을 노트에 써봐도 좋을것 같다.

이제 answer 배열 안에는 [1, 2, 3, 4] 중 3개를 뽑아 합을 구한 값이 들어가 있을 것이다.

answer.filter(v => isPrime(v)) 로 소수를 찾고, length를 이용해서 그 갯수를 최종으로 return해주고 있다.

function solution(nums) {
    var answer = []
    
    const dfs = (nums, cnt, sum) => {
        if(cnt === 3){
            answer.push(sum)      
        } else{
            for(let i = 0; i < nums.length; i++){
                dfs(nums.slice(i+1), cnt+1, sum+nums[i])
            }
        }
    }
    dfs(nums, 0, 0)
    answer = answer.filter(num=>isPrime(num))
    
    return answer.length;
}

생각해보니 cnt === 3 조건을 만족할 경우 계속 reduce함수를 호출하고 있다. 더 효율적으로 코드를 설계하기 위해 위와같이 바꿔주었다.