[프로그래머스] Lv.1 소수 만들기 - JavaScript

문제 설명

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

 

제한 사항

• nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다.
• nums의 각 원소는 1 이상 1,000 이하의 자연수이며, 중복된 숫자가 들어있지 않습니다.

 

입출력 예

numbers	result
[1,2,3,4]	1
[1,2,7,6,4]	4

 

문제 풀이

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

function solution(nums) {
    var answer = 0;
    
    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++){
                let sum = nums[i]+nums[j]+nums[k];
                if(isPrime(sum)){
                    answer++;
                }
            }
        }
    }
    
    return answer;
}

 

이번 문제는 비교적 쉽게 풀었다. 다만 처음에 3중 for문을 작성했을때 3개 다 범위를 nums.length로 지정했는데, 그렇게 할 경우 k가 j보다 작아질 수 있어서 i는 nums.length-2까지, j는 nums.length-1까지 k는 nums.length까지로 범위를 수정하였다. 그리고 소수를 판별하는 함수를 선언해서 소수일 경우에 answer을 증가시키는 식으로 해서 결과적으로 소수가 되는 경우의 개수를 반환하였다. 

 

다른 풀이

function combination(nums, arr, index, r, target) {
    if (r == 0) {
        const sum = arr.reduce((a,b) => a + nums[b], 0);
        
        if(isPrime(sum)) ++answer;
    } else if (target == nums.length) {
        return;
    } else { 
        arr[index] = target;
        
        combination(nums, arr, index + 1, r - 1, target + 1); 
        combination(nums, arr, index, r, target + 1); 
    } 
}

 

다른 풀이를 찾아봤는데 3중 for문을 돌리는 방식이 아닌 재귀 방식으로 combination을 구현한 예시가 있었다. nums 배열에서 r개를 고르는 조합을 구하면서, 그 조합의 합이 소수일 경우에 answer++을 하는 방식이다. 

 

어떻게 이런 방식을 생각해 낼 수가 있지....! 앞으로 코테를 풀면서 더 많은 방법들을 찾아봐야겠다!