[JS] 프로그래머스 Lv.2 : 소수 찾기 - 완전 탐색

ahyes·2023년 4월 28일
0

이 문제는 두가지 방법으로 풀 수 있습니다.

첫 번째는 만들 수 있는 가장 큰 수를 찾아 그 수 이하의 모든 소수를 구해 numbers의 숫자가 포함되어 있는지 확인하는 방법.
두 번째는 만들 수 있는 모든 수를 구해(DFS) 소수인지 아닌지 판별하는 방법.

첫 번째 방법은

function solution(numbers) {
    let answer = 0;
    let arr = [];
    numbers = numbers.split("").sort((a,b)=> b-a).join("");

    for(let i = 0; i<= numbers; i++)arr.push(i);
    arr[1] = 0;
    for(let i = 2; i< arr.length; i++){
        if(!arr[i])continue;
        for(let j = i*2; j<= numbers; j+=i){
            arr[j] = 0;
        }
    }
    arr.filter(x => x).map(x =>{
        let mini_numbers = numbers.toString().split("");
        let mini_x = x.toString().split("")
        
        for(let i = 0; i <= mini_x.length; i++){
            if(mini_numbers.includes(mini_x[i])){
                mini_numbers[mini_numbers.indexOf(mini_x[i])] = 'x';
                mini_x[i] = 'x';
            }
        }
        if(mini_x.filter(x => x!= "x").length === 0)answer++;
    })
    
    return answer;
}

두 번째 방법은 DFS 도중도중 set에 만들어진 문자열을 넣어주는 방식.

function solution(numbers) {
    var answer = new Set();
    let check;
    
    function dfs(num,i,str){
        check[i] = true;
        str+=num;
        answer.add(str*1);
        for(let j = 0; j<check.length;j++){
            if(!check[j])dfs(numbers[j],j,str);
        }
        check[i] = false;
    }
    
    for(let i = 0; i<numbers.length; i++){
        check = new Array(numbers.length).fill(false)
        dfs(numbers[i],i,"");
    }
    let arr = [...answer];
    for(let i = 0; i<arr.length; i++){
        for(let j = 2; j<arr[i];j++){
            if(arr[i]%j === 0)arr[i] = 0;
        }   
    }
    return arr.filter(x => (x !== 0)&&(x !== 1)).length;
}
profile
프론트엔드 공부를 해봅시다

0개의 댓글