[ Lv. 2 ] 소수 찾기 - JavaScript

문제 설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

제한사항

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

 

입출력 예

numbers	return
"17"	3
"011"	2

 

입출력 예 설명

예제 #1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

예제 #2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

• 11과 011은 같은 숫자로 취급합니다.

---

내풀이

function solution(numbers) {

    let nums = numbers.split("");
    let setNum = new Set();

    getPermutation(setNum, nums, '');

    return setNum.size;
}


function getPermutation(setNum, arr, nextString) {
    if (arr.length > 0) {
        for (let i = 0; i < arr.length; i++) {
            let newNextString = Number(nextString + arr[i]);
            let copyArr = [...arr];
            copyArr.splice(i, 1);

            if (isPrime(newNextString)) {
                setNum.add(newNextString);
            }

            getPermutation(setNum, copyArr, newNextString);
        }
    }
}

function 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에 대한 부분은 아직 학습하지 않았기 때문에 재귀를 이용한 방식으로 풀어보기로 했다.

---

크게 생각해봤을 때 다음과 같은 순서로 접근하면 되겠다고 생각했다.

1. 주어진 숫자 카드로 나올 수 있는 숫자의 조합 구하기 ( 재귀 함수 이용 )

2. 소수가 아닌 수 제거하기 ( set을 이용해서 중복되는 숫자 제거 )

3. 소수 여부 판별하기 ( 에라토스테네스의 체 or 반복문 )

---

1번의 경우 숫자 조합을 구하기 위해서 getPermutation 함수를 생성하고, 첫 번째 인자로 set 객체로 생성된 변수를 넣고, 두 번째 인자로 선택되지 않은 숫자가 담긴 배열, 세 번째 인자로 현재 선택된 숫자가 문자열 형태로 담긴다.

선택되지 않은 숫자가 아직 있다면 다음에 들어갈 문자 조합과 합쳐서 재귀로 반복될 함수에서 3번째 인자에 새롭게 갱신되어 들어가게 된다. 선택된 숫자를 다음 재귀에서는 제외해야하기 때문에 새롭게 복사해서 splice로 해당 원소를 지우고 그 변수를 2번째 인자에 갱신해준다. 

getPermutation 함수가 재귀적으로 반복됨에 따라 합쳐진 숫자의 조합이 소수인지 판별하고, 소수로 판별되는 경우 첫 번째 인자로 전달받은 setNum 변수에 추가해준다. (중복되는 것에 대해서는 알아서 제거되기 때문에 고유의 숫자 조합만 남게 된다.)