javascript - 소수 만들기

문제 설명

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

 

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

 

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

input으로 주어진 nums 숫자 배열에서 3개의 숫자를 뽑아 합을 구했을 때, 소수가 되는 경우의 수를 구하는 문제이다.

 

[answer1 - for문으로 모든 경우 탐색]

function solution(nums) {
    var answer = 0;
    var leng = nums.length;
    
    for(let i=0 ; i<leng ; i++) {
        for(let j=i+1 ; j<leng ; j++) {
            for(let k=j+1 ; k<leng ; k++) {
                var result = nums[i] + nums[j] + nums[k];
                var check = isSosu(result);
                if(check)   answer++;
            }
        }
    }
    
    return answer;
}

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

이전에 소수 구하는 문제를 DFS를 사용해서 푼 적이 있는데 접근 방법이 쉽게 떠오르지 않아 그냥 단순히 3중 for문을 사용하여 모든 경우를 탐색하였다.

그리고 isSosu라는 함수에서 해당 케이스가 소수인지를 판명한다.

for문으로 모든 경우를 탐색하기 때문에 명료하고 이해하기 쉽다.

 

[answer2 - DFS로 탐색]

var answer = 0;
var numArr = [];

function findDFS(index, sum, level) {
    // level이 3일때
    if(level === 3) {
        // 소수인지 판정하기
        var check = 0;
        for(var i=2 ; i<sum ; i++) {
            if(sum % i === 0) {
                check=1;
                break;
            }
        }
        if(check === 0) answer++;
        return;
    }
    // numArr의 마지막 값을 넘었을 때
    if(index === numArr.length)   return;
    
    // 그 외의 경우
    else {
        findDFS(index+1, sum+numArr[index], level+1);
        findDFS(index+1, sum, level);
    }
}

function solution(nums) {
    numArr = nums;
    findDFS(0,0,0);
    return answer;
}

DFS를 사용하여 경우를 탐색하는 코드이다. nums 배열 중 몇 번째 요소를 탐색할 지에 대한 index, 이때까지 더한 수의 합인 sum, 몇 번째 숫자를 더하고 있는지에 대한 level이라는 3개의 파라미터를 받는 함수이다. 

 

level이 3이되면 3개의 숫자를 모두 더했다는 의미이므로, 3개 숫자의 합인 sum 이 소수인지를 판명한다. 소수이면 answer을 더해주고 return 해준다.

index가 nums 배열의 최대 개수를 넘으면 참조할 숫자가 없기 때문에 return 해준다.

그 외에 모든 경우에는 재귀적으로 findDFS 함수를 호출하여 모든 케이스를 탐색할 수 있도록 한다.

 

 

DFS를 사용하는 문제가 많기 때문에 아래의 연습을 통해 사용하는데 있어 익숙해지도록 노력해야겠다.

• DFS를 구성할 파라미터 잘 생각하기
• 재귀함수 규칙 찾기
  • 어떻게 하면 모든 경우를 탐색할 수 있을지!
• 베이스케이스 잘 설정하기