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

🔗 문제 링크

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

프로그래머스

✏️ 풀이

function solution(numbers) {
    const primes = Array(1_000_000).fill(true);
    primes[0] = false;
    primes[1] = false;
    
    for (let i = 2; i <= 1000; i++) {
        for (let j = i * 2; j < 1_000_000; j += i) {
            primes[j] = false;
        }
    }
    
    const primeList = {};
    
    const dfs = (nums, selected = Array(nums.length).fill(false), comb = '') => {
        const num = Number(comb);
        let count = 0;
        if (primes[num] && !primeList[num]) {
            primeList[num] = true;
            count += 1;
        }
        for (let i = 0; i < nums.length; i++) {
            if (selected[i]) {
                continue;
            }
            selected[i] = true;
            count += dfs(nums, selected, comb + nums[i]);
            selected[i] = false;
        }
        return count;
    };
    
    return dfs(numbers);
}

먼저 numbers의 최대 길이가 7이므로, 1부터 1,000,000까지의 모든 자연수 중에서 소수를 구한다. 그 다음 numbers의 숫자들로 조합 가능한 모든 경우를 확인한다.

 

함수 dfs는 먼저 숫자들을 이어붙인 문자열을 숫자로 변환한 후, 이 수가 소수라면 count를 1 증가시킨다. 그리고 나서 현재 문자열에 1개의 숫자를 이어붙인 조합을 인수로 전달하며 재귀호출한다. 그리고 나서 재귀호출의 리턴값만큼 count를 증가시킨다. 이렇게 하여 최종적으로 모든 경우에 대해 탐색을 완료한 뒤 합계된 count를 얻을 수 있다. 이 때, 중복된 경우가 발생할 수 있으므로 primeList에 한 번 등장한 조합의 수를 저장하여 중복되지 않는 수만 카운트