[프로그래머스 / JS] 소수 찾기 - Level 2

🚩 문제 주소

프로그래머스

 

📄 접근 방법

 

완전탐색 - 백트래킹..?

 

일단 만들어진 숫자를 소수인지 판단을 하기 위해서 에라토스테네스의 체를 이용하여 소수 판별 함수를 만들었습니다.

 

주어진 숫자 문자열을 이용해서 가능한 모든 숫자를 백트래킹 알고리즘을 이용하여 구해주었습니다.

하지만 '11'과 '011'은 같은 숫자인 것으로 판단하는 게 조건이기 때문에 Set을 이용하여 중복을 제거해 주었습니다.

 

구한 숫자들을 소수 판별 함수에 전달해서 판단 후, 소수가 맞다면 answer를 1씩 증가시켜줍니다.

 

---

👨‍💻 나의 코드

const isPrime = (num) => { // 에라토스테네스의 체
    if (num < 2) return false;
    for (let i=2; i<=parseInt(num**0.5); i++) {
        if (num % i === 0) return false;
    }
    return true;
}

function solution(numbers) {
    let answer = 0;
    const set = new Set();
    const visited = Array(numbers.length).fill(0);
    
    const makeNumbers = (depth, str) => {
        if (depth === numbers.length) return;
        for (let i=0; i<numbers.length; i++) {
            if (!visited[i]) {
                visited[i] = 1;
                set.add(parseInt(str+numbers[i]));
                makeNumbers(depth+1, str+numbers[i]);
                visited[i] = 0;
            }
        }
    }
    makeNumbers(0, "");
    
    set.forEach(v => {
        if (isPrime(v)) answer++;
    });
    
    return answer;
}