[프로그래머스] 소수 찾기 (level2, js)

 

문제

---

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

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

 

문제조건

---

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

 

풀이

---

주어진 숫자들의 순열을 만들어 소수인지를 판별하면 되는 문제. 우선 주어진 문자열을 숫자들로 만들기 위해 split 메서드를 사용하였다. javascript로는 순열을 만들어보지 않아서 생각보다 어려웠다. js는 배열을 쉽게 자를 수 있다는 점을 활용하여 순열을 만들면 된다. 

지금까지 선택되지 않은 수들은 arr에, 선택된 수들은 fixed에 자리잡게 된다. 선택된 수가 이미 만들어져 있는 수인지, 소수인지를 판별하여 answer배열에 넣었다. 재귀를 사용해 모든 경우의 수를 다 따질 수 있도록 하였다. 결과적으로 answer 배열에는 조건을 만족하는 수들만 있게 된다. 

 

코드

---

function solution(numbers) {
    const answer = [];
    let nums = numbers.split(''); 
    
    // 소수 판별
    const isPrimeNum = (num) => {
        if(num<=1) return false;
        for (let i = 2; i*i <= num; i++) {
            if (num % i === 0) return false;
        }
        return true;
    }
    
    // 순열 만들기
    const getPermutation = (arr, fixed) => {
        if(arr.length >= 1) {
            for (let i=0; i<arr.length; i++) {
                const newNum = fixed + arr[i];
                const copyArr = [...arr];
                copyArr.splice(i, 1);
                if (!answer.includes(+newNum) && isPrimeNum(+newNum)){
                    answer.push(+newNum) 
                }
                getPermutation(copyArr, newNum); 
            }
        }
    }
    
    getPermutation(nums, '');
    return answer.length;
}