문제 링크

바로가기

문제 풀이

function solution(numbers) {
    let answer = 0;
    const nums = numbers.split("");
    const check = new Array(10000000).fill(0);
    const length = new Array(numbers.length).fill(false);
    
    check[0] = true;
    check[1] = true;
    const dfs = (number, str) => {
        let num;
        if(number !== "") num = Number(str);
        
        if(!check[num]) {
            let flag = true;
            for(let i = 2; i * i <= num; ++i) {
                if (num % i === 0) flag = false;
            }
            
            if(flag) answer++;
            check[num] = true;
        }
        for(let j = 0; j < number.length; ++j) {
            if(length[j] === false) {
                length[j] = true;
                dfs(number, str + number[j]);
                length[j] = false;
            }
        }
    }
    
    dfs(nums, "");
    return answer;
}

새롭게 배운 점

너무 어려웠던 소수찾기 문제

모든 경우의 수를 다 찾아봐야하기 때문에 dfs로 탐색하였다.

중복해서 숫자를 검색할 필요는 없기 때문에 check 배열로 이미 찾은 수를 확인해주었고, 배열의 길이만큼 반복문을 돌려주면서 원소 한 개 넣고 검사하고 한개 더 넣고 검사하는 방식으로 모든 경우의 수를 탐색해주었다.