한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 numbers
가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.
제한사항
numbers
는 길이 1 이상 7 이하인 문자열입니다.numbers
는 0~9까지 숫자만으로 이루어져 있습니다.입출력 예
numbers | return |
---|---|
"17" | 3 |
"011" | 2 |
입출력 예 설명
예제 #1
[1, 7]
으로는 소수 [7, 17, 71]
를 만들 수 있습니다.
예제 #2
[0, 1, 1]
으로는 소수 [11, 101]
를 만들 수 있습니다.
소스코드
// 가능한 모든 경우 구하기
function dfs(base, array) {
let nums = [];
for (let i=0; i<array.length; i++) {
let push = base.concat(array[i]);
nums.push(Number(push));
let visit = [...array];
visit.splice(i, 1);
if (visit.length !== 0) {
let arr = dfs(push, visit);
nums.push(...arr);
}
}
return nums;
}
// 소수 판정 함수
function isPrime(input) {
if (input < 2) {
return false;
}
for (let i=2; i<=Math.sqrt(input); i++) {
if (input%i == 0) return false;
}
return true;
}
function solution(numbers) {
var primeCnt = 0;
let num = numbers.split("");
let possibleNum = dfs("", num);
// 중복 제거
let set = new Set(possibleNum);
possibleNum = [...set];
for (let i=0; i<possibleNum.length; i++) {
if (isPrime(possibleNum[i])) primeCnt++;
}
return primeCnt;
}