// 종이 조각을 조합해서 소수를 몇 개 만들 수 있는지 알아내는 문제
function solution(numbers) {
const numArr = numbers.split("");
const prime = []
// 소수인지 판별하는 함수
function isPrime(num){
if( num <= 1) return false;
for(let i = 2; i <= Math.sqrt(num); i++){
if(num % i === 0) return false; // 2부터 제곱근까지 나눠보면서 나눠지면 소수가 아님
}
return true;
}
// arr는 아직 조합되지 않은 숫자 조각의 배열
// fixed는 이전까지 조합된 숫자 조각들
const checkNum = (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);
// 중복을 피하기 위해 배열에 포함되어있지 않고 소수면 배열에 추가
// 조합된 숫자가 앞에 0이 붙는 경우가 있어서 number로 바꿔 0을 제외하기 위해서 붙임
if(!prime.includes(+newNum) && isPrime(newNum)){
prime.push(+newNum)
}
checkNum(copyArr, newNum);
}
}
}
checkNum(numArr, '');
return prime.length; // 소수 배열의 개수 리턴
}
function solution(numbers) {
const answer = [];
const arr = numbers.split('');
function isPrimeNum(num) {
if (num <= 1) return false;
for (let i = 2; i <= Math.sqrt(num); i++) {
if (num % i === 0) return false;
}
return true;
}
// dfs를 이용하여 numbers를 한자리로 자른 모든 경우의 수를 탐색합니다.
function dfs(arr, fix) {
if (arr.length >= 1) {
for (let i = 0; i < arr.length; i++) {
const newFix = fix + arr[i];
const newArr = arr.slice();
newArr.splice(i, 1);
// 중복되지않고 소수인 경우 answer배열에 push 해줍니다.
if (!answer.includes(+newFix) && isPrimeNum(+newFix)) answer.push(+newFix);
dfs(newArr, newFix);
}
}
}
dfs(arr, '');
return answer.length;
}
//한자리 숫자가 적힌 종이들, 종이들을 붙여 소수를 몇개 만들 수 있는지
// 각 종이는 0~9, numbers길이는 최대 7개, 최대 경우의 수 => 7! 5000개로 충분히 다 만들어 볼 수 있다.// 검사하는데 시간복잡도각 괜찮다면 완전탐색 가능
//어떻게 만들까? for문을 원하는 만큼 돌릴수 있는 DFS이용
function solution(numbers){
const nums=numbers.split("").map(v=>+v);
const l=nums.length;
const visited=Array.from({length:l}, ()=>false);
// 중복검사를 위해 set사용
const answer=new Set();
//소수확인 함수
function isPrime(number){
//예외처리
if(number===0)return false;
if(number===1)return false;
if(number===2)return true;
const a=Math.sqrt(number);
let b=2;
while(b<=a){
if(number%b ===0 )return false;
b++;
}
return true;
}
function DFS(depth, result){
//answer에 있는 수는 검사 필요x
if(!answer.has(+result) && isPrime(+result))answer.add(+result);
if(depth===l){
return;
}else{
for(let i =0 ; i<l; i++){
if(!visited[i]){
visited[i]=true;
const n = nums[i];
DFS(depth+1, result+n);
visited[i]=false;
}
}
}
};
DFS(0, "");
return answer.size
}
// 가능한 순열을 배열에 담아 리턴 - 중복 허용
// [0, 1, 1] 중 selectedNumber개에 대한 순열을 구합니다.
function getPermutationArr(numArr, selectedNumber) {
const result = [];
if (selectedNumber === 1) return numArr;
numArr.forEach((fixed, index, origin) => {
const rest = [...origin.slice(0, index), ...origin.slice(index + 1)];
const permutations = getPermutationArr(rest, selectedNumber - 1);
const attached = permutations.map((permutation) => [fixed, ...permutation].join(''));
result.push(...attached);
})
return result;
}
function isPrime(number) {
if (number <= 1) return false;
for (let i = 2; i <= Math.sqrt(number); i++) {
if (number % i === 0) return false;
}
return true;
}
function solution(numbers) {
const numArr = numbers.split('')
const permutationArr = []
// 숫자 중 1개 순열, 2개 순열, ... , numArr.length개(전체) 수열
for (let i = 1; i <= numArr.length; i++) {
permutationArr.push(...getPermutationArr(numArr, i).map(str => +str))
}
const setPermutationArr = [...new Set(permutationArr)]
return setPermutationArr.reduce((acc, number) => isPrime(number) ? acc + 1 : acc, 0)
}
function solution(numbers) {
let answer = 0;
const memory = {}; // 소수를 저장하는 객체
const visit = Array.from({length : numbers.length}, () => false); // 방문 체크 배열
function isPrime(n){
if(n <= 1) return false;
// 왜 루트n 까지만 탐색하면 되는지 알아보면
// 36의 약수를 보면 1, 2, 3, 4, 6, 9, 12, 18, 36 이있습니다
// 루트36인 6은 약수들 중 가운데 수라고 보면 됩니다.
// 2 * 18, 3 * 12, 4 * 9 이런 식으로 6보다 작은 약수는 6보다 큰 약수와 짝지을 수 밖에 없습니다.
// 즉 2를 찾았다면 18은 이미 탐색한거나 마찬가지입니다.
// 그래서 루트 n까지만 탐색해도 소수인지 아닌지 판별이 가능합니다.
for(let i = 2; i <=Math.sqrt(n); i++){
if(n % i === 0) return false;
}
return true;
}
function DFS(N, temp){
// temp가 빈문자열이 아니고 && memory에 없고 && 소수라면
// memory에 저장해줍니다.
if(temp.length && !memory[+temp] && isPrime(+temp)){
memory[+temp] = true;
}
// 탈출조건 (재귀 코드의 핵심)
if(N >= numbers.length){
return;
}
// 해당 문제는 조합은 아니고 순열을 찾는 문제입니다.
// 중복 순열은 아니므로 visit 배열로 조각을 골랐는지 아닌지 판별해야합니다.
for(let i = 0; i<numbers.length; i++){
if(!visit[i]){
visit[i] = true;
DFS(N, temp + numbers[i]);
visit[i] = false;
}
}
}
DFS(0, "");
return Object.keys(memory).length;
}
// 해당문제에서 에라토스 머시기는 최악의 경우 9999999 자리의 배열을 만들어야 하므로
// 조금 비효율적인 면이 있습니다. 직접 해보진 않아서 더 빠를진 잘 가늠이 안갑니다.
function isPrime(n) {
if(n<2) return false;
for(let i = 2; i<= Math.sqrt(n); i++){
if(n % i === 0) return false;
}
return true;
}
function solution(numbers) {
// 1. 숫자 하나씩 떼어내기
// 2. 가능한 숫자의 순열 만들기!
// 3. 소수인지 판별해서 개수 세기
const answer = [];
let numArr = numbers.split('');
function permutation (arr, fixNum) {
if(arr.length >= 1){
for(const i of arr){
let newNumber = fixNum + i;
// 0으로 시작하는 순열의 경우 예외처리
newNumber[0] === '0' ? newNumber = newNumber.slice(1):'';
const copyArr = [...arr];
copyArr.splice(arr.indexOf(i),1); // 고정할 숫자 제외하고 나머지 숫자 배열 가져오기
console.log(newNumber, copyArr)
if(!answer.includes(newNumber) && isPrime(newNumber)){ //중복X + 소수일때만 push
answer.push(newNumber)
}
permutation(copyArr, newNumber);
}
}
}
permutation(numArr,'');
return answer.length
}