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

문제

문제 설명

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

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

제한사항

numbers는 길이 1 이상 7 이하인 문자열입니다.
numbers는 0~9까지 숫자만으로 이루어져 있습니다.
"013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

입출력 예

numbers return
"17" 3
"011" 2

풀이

function solution(numbers) {
    var answer = 0;
    let arr = numbers.split("").map((v)=>+v);
    let visited = Array.from({length:arr.length}, ()=>0);
    let temp = [];
    let res = [];
    
    const dfs = (v) =>{
         if(v === arr.length){
            const isPrm = isPrime(+temp.join(""));
             if(isPrm) res.push(+temp.join(""))
         }
        else{
              for(let i=0; i<arr.length; i++){
                if(visited[i] === 0){
                    visited[i] = 1;
                    temp.push(arr[i]);
                    dfs(v+1);
                 	temp.pop()
                    visited[i] = 0;
                }
        }
             
         }  
       
    }
    
    for(let i=0; i<arr.length; i++){
        dfs(i);
    }
    
    //중복제거
    const set = new Set(res);
    // console.log([...set])
    
    answer = [...set].length;
    
    return answer;
}

//소수 구하기
const isPrime = (num) =>{
    if(num <= 1) return false;
    for(let i=2 ; i<= +Math.sqrt(num); i++){
        if(num % i ===0 )return false;
    }
        
    return true;
    
}

• dfs로 순열을 구하는 것이 중요했다

• set이용 중복제거하기

   //res = [2,3,3,4,5]
   const set = new Set(res);
   cibsike.log([...set]) // [2,3,4,5]
  

• 소수 구하기

  	- 예를들어 num이 17일때, 17을 2부터 Math.sqrt(num)=== 4 까지로 나누어서 나누어 떨어지지 않으면 소수이다