[프로그래머스] 소수 찾기 (JS) - 완전탐색, DFS

문제

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

프로그래머스

코드

function solution(numbers){
    const answer = [];
    const nums = numbers.split('');
    const length = nums.length;
    const isVisited = Array.from({length:length}, ()=>false);
    const arr = Array.from({length:length}, ()=>0);
    
    function dfs(cnt){
    	if(cnt!==0){
            let s = '';
            for(let i=0; i<cnt; i++){
            	s+=arr[i];
            }
            if(isPrime(Number(s))) answer.push(Number(s));
        }else if(cnt===length) return;
        
        for (let i=0; i<length; i++){
        	if(!isVisited[i]){
            	isVisited[i]=true;
                arr[cnt]=nums[i]
                dfs(cnt+1)
                isVisited[i]=false;
            }
        }
    }
    
    dfs(0);
	
    return [...new Set(answer)].length
}

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

정리

소수 판별 함수

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

 

string 배열화

const nums = numbers.split(''); // '123' -> ['1', '2', '3']

 

배열 초기화 - Array.from({length: ...}, ()=>{})

const isVisited = Array.from({length:length}, ()=>false);
const arr = Array.from({length:length}, ()=>0);

 

참조

https://velog.io/@kler/%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8-%EB%B0%B0%EC%97%B4-%EC%83%9D%EC%84%B1-%EC%B4%88%EA%B8%B0%ED%99%94-%ED%95%9C%EB%B2%88%EC%97%90-%ED%95%98%EA%B8%B0