프로그래머스 - 소수 찾기

✨ Lv. 2 - 소수 찾기

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42839

문제 설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

제한사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

풀이 코드 + 설명

숫자가 적힌 종이 조각을 각각 1, 2, 3, ... n개를 어떤 순서에 따라 선택했냐에 따라 만들 수 있는 숫자의 가짓수는 다양해집니다. 이를 DFS를 이용하여 풀이해봅시다.

우선 선택 여부를 판단할 selected 배열을 선언하여 모든 값을 false로 초기화합니다. 이후, DFS를 반복하여, 매번 선택한 카드들에 대해 소수인지 판단하여 소수일 경우에는 결과를 담을 result에 add합니다. 여기서 result는 중복을 방지하기 위해서 Set을 사용합니다.

이후, result에 담긴 원소의 개수를 return 하여 문제를 해결합니다.

function solution(numbers) {
    const result = new Set();
    const selected = new Array(numbers.length).fill(false);
    
    function DFS(current) {
        if(isPrime(Number(current))) result.add(Number(current)); 
        [...numbers].forEach((v, i) => {
            if(!selected[i]) {
                selected[i] = true;
                DFS(current + v);
                selected[i] = false;
            }
        })
    }
    DFS("");
    
    return [...result].length;
}

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