[프로그래머스] (LV1) 소수 만들기

소수 만들기

JavaScript, Python

문제 설명

주어진 숫자 중 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을 만들 수 있습니다.

풀이

---

javascript

function solution(nums) {
    var answer = 0;
    
    function isPrime(n){
        for(let i = 2, s= Math.sqrt(n); i <= s; i++)
            if(n % i === 0) return false;
        return n > 1;
    }
    
    function get(value,count,arr){
        if(count === 2){
            arr.forEach((a)=>{
                var currentValue = value+a
                if(isPrime(currentValue)){  
                    answer++;
                }
            })
        }else{
            arr.forEach((a,i)=>{
                var newArr = JSON.parse(JSON.stringify(arr)).slice(i+1)
                get(value+a,count+1,newArr)
            })
        }
    }
    
    get(0,0,nums);
    
    return answer;
}

python

from itertools import combinations
def solution(nums):
    answer = 0
    
    def isPrime(n):
        if n < 2: 
            return False 
        for i in range(2, int(n ** 0.5) + 1): 
            if n % i == 0: 
                return False 
        return True

    for v in list(combinations(nums, 3)):
        if isPrime(sum(v)):
            answer+=1;
    return answer

설명

---

BFS 방법으로 3개를 골라 소수 확인을 하면 된다.

javascript 풀이는 재귀함수를 이용해 3번을 반복했다.

python 풀이는 itertools 패키지의 combinations 함수를 사용해 조합을 구했다.