[JS] 프로그래머스 - 소수 찾기

📌 문제

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

 

💡 아이디어 

순열 + 소수 찾기 + Set 환장 조합..

 

✏️ 풀이

function solution(numbers) {
    const arr = numbers.split('');
    const primeSet = new Set();
    // 같은 수가 여러 번 나올 수 있으니까 Set으로 중복 제거해주기
    
    for(let i=1; i<=numbers.length; i++) {
        const permutaion = permutations(arr, i);
        for(let i=0; i<permutaion.length; i++) {
           if(isPrime(Number(permutaion[i].join("")))){
               primeSet.add(Number(permutaion[i].join("")));
              }                 
        }
    }
    return primeSet.size;
}


// 조합해서 나올 수 있는 모든 수 구하기(순열)
function permutations(arr, num) {
    const result = [];
    if(num === 1) return arr.map((el) => [el]);
    
    arr.forEach((fixed, index, origin) => {
        const rest = [...origin.slice(0, index), ...origin.slice(index+1)];
        const permutation = permutations(rest, num - 1);
        const attached = permutation.map((el) => [fixed, ...el]);
        result.push(...attached);
    })
    return result;
} 

// 소수 판별
function isPrime(num) {
    if(num === 1 || num === 0) return false;
    for(let i=2; i<=Math.sqrt(num); i++) {
        if(num % i === 0) return false;
    }
    return true;
}