프로그래머스 | 소수 찾기

📍문제 설명📍

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

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

---

📚입출력 예시📚

---

💯성공한 풀이💯

const solution = (numbers) => {
    let num = numbers.split('');
    let numSet = new Set();
    
    dfs(numSet, num,'');
    
    return numSet.size;
}

const dfs = (set, arr, fixed) => {
    if(arr.length >= 1) {
        for(let i = 0; i < arr.length; i++) {
            let newFixed = fixed + arr[i]; 
            let newArr = [...arr];
            newArr.splice(i, 1);
            
            if(isPrime(parseInt(newFixed))) {
            set.add(parseInt(newFixed));
            }
            
            dfs(set, newArr, newFixed);
        }
    }
}

const isPrime = (num) => {
    if(num < 2) return false
    for(let i = 2; i <= Math.sqrt(num); i++) {
        if(num % i === 0) return false
    }
    return true;
}

💡문제 접근 방식💡

완전 탐색 문제이기 때문에 dfs를 먼저 생각했다.

중복을 없애기 위하여 set을 사용하였다.

1번 예시로 설명을 하면,
fixed 가 처음 값으로는 공백이 들어오기때문에
newFixed 값은 1 이 된다.
newArr.splice(i, 1)로 현재 인덱스를 고정하고,
newArr을 재귀 함수의 매개변수로 넘겨준다.
소수 판별 후 set 자료구조의 크기를 return 한다.

i = 0;
newFixed = ''
newArr = ['1', '7']
newArr.splice(i, 1) => newArr['7']

	dfs(set, newArr => ['7'], '1')
		i = 0;
       	newFixed = '17'
    	newArr = ['7']
    	newArr.splice(i, 1) -> newArr[]

i = 1;
newFixed = '7'
newArr = ['1', '7']
newArr.splice(i, 1) => newArr['1'], '7')

	dfs(set, newArr => ['1']
    	i = 0;
        newFixed = '71'
        newArr.splice(i, 1) -> newArr[]