풀이
김영준
// 종이 조각을 조합해서 소수를 몇 개 만들 수 있는지 알아내는 문제 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 }