한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.
numbers | return |
---|---|
"17" | 3 |
"011" | 2 |
예제 #1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.
예제 #2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.
getCombinations
함수는 입력된 숫자로 가능한 모든 조합을 생성하는 역할을 한다. 이 함수는 깊이 우선 탐색 (DFS)을 사용하여 가능한 모든 조합을 찾는다. 각 숫자 조합은 문자열 형태로 저장되며, 이후 정수로 변환되어 반환된다.isPrime
함수는 주어진 숫자가 소수인지를 판별한다. 이 함수는 숫자가 2보다 작거나, 2로 나누어지지 않는지, 제곱근까지의 모든 숫자로 나누어지지 않는지를 확인하여 소수 여부를 판단한다.solution
함수는 getCombinations
함수를 사용하여 가능한 모든 조합을 생성하고, 중복된 조합을 제거한다. 그런 다음 isPrime
함수를 사용하여 각 조합이 소수인지를 확인하고, 소수인 조합의 개수를 반환한다. 가능한 모든 조합을 생성하고 중복을 제거하기 위해서 Set
을 사용하였다.✅ 답안
function solution(numbers) {
const set = [...new Set(getCombinations(numbers))];
return set.filter((v) => isPrime(v)).length;
}
const getCombinations = (str) => {
const answer = [];
let visited = new Array(str.length).fill(false);
const dfs = (cur) => {
answer.push(+cur);
for (let i = 0; i < str.length; i++) {
if (!visited[i]) {
visited[i] = true;
dfs(cur + str[i]);
visited[i] = false;
}
}
};
dfs('');
return answer;
};
const isPrime = (N) => {
if (N < 2) return false;
for (let i = 2; i <= Math.sqrt(N); i++) {
if (N % i === 0) return false;
}
return true;
};