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

문제

https://programmers.co.kr/learn/courses/30/lessons/42839

문제 풀이

코드

//소수 검증 함수
function isPrime(num){
    if(num<=1) return false; 
    for(let i=2; i<=parseInt(num/2); i++){
        if(num%i===0) return false;
    }
    return true;
}
function solution(numbers) {  
    let cnt=0, tmp=[], answer=[];
    const arrNum=numbers.split('').map(v=>Number(v));
    const ch=Array.from({length:arrNum.length}, ()=>0);
    for(let i=1; i<=arrNum.length; i++){
        DFS(0, i); //arrNum에서 i개의 숫자를 뽑음
    }
    
    function DFS(L, r){
        if(L===r){
            if(!answer.includes(parseInt(tmp.join(''))) && isPrime(parseInt(tmp.join('')))){
                answer.push(parseInt(tmp.join('')));  
            }
        }
        else{
            for(let i=0; i<arrNum.length; i++){
                if(ch[i]===0){
                    ch[i]=1;
                    tmp[L]=arrNum[i];
                    DFS(L+1, r);
                    ch[i]=0;
                }
            }
        }
    }
    return answer.length;
}

순열 구하는것을 엄청 헤매서 오래 걸린 문제이다.

for(let i=1; i<=arrNum.length; i++){
        DFS(0, i); //arrNum에서 i개의 숫자를 뽑음
}

와 같이, for문을 통해 몇개를 뽑는지, i의 개수를 바꿔가면서 DFS를 호출하는 것이 관건이였다.
이방법에 대한 해답은 예전에 푼 문제인 순열구하기에서 찾을 수 있었다. DFS는 연습만이 답이다🔥
순열, 조합구하는 알고리즘을 익히자.

참고

• https://hihellloitland.tistory.com/88
• https://velog.io/@rladpwl0512/8-10-%EC%88%9C%EC%97%B4-%EA%B5%AC%ED%95%98%EA%B8%B0 (순열구하기 문제)