문제
문제 설명
한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.
제한사항
- numbers는 길이 1 이상 7 이하인 문자열입니다.
- numbers는 0~9까지 숫자만으로 이루어져 있습니다.
- "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.
1차 결론 - 못풀었다.
무슨 숫자가 있는지까지는 저번 자릿수구하기 문제 풀이덕에 구할 수 있었는데 숫자를 조합시키는 방법을 모르겠다..
<생각들>
숫자조합으로 만들어낼 수 있는 소수 개수 구하기
받은 숫자에 어떤 숫자들이 들어있는지를 알아야 조합을 구할 수 있다.
소수는 1과 자기자신으로만 나눠떨어진다. //최대공약수는 1
배열 요소 반복을 이용해 요소들을 돌아가면서 조합시키고 싶다..
<사고 과정>
1.numbers를 문자열로 만들기
2.실제 숫자를 구하기 위해 realNumber 변수 선언
3.실제 숫자가 어떤 수로 이루어졌는지 알기 위해 arrNum 배열 선언
4.numbers길이만큼 0부터 숫자 덧셈을 반복해 실제 숫자와 실제 숫자의 숫자 요소 배열 할당
5.구한 숫자 요소 배열을 반복문을 돌려 조합들을 생성해내고 싶은데 어떻게 해야할지 모르겠음.
모르겠는 포인트 : 앞에서부터 뒤까지 숫자만큼 돌리기와 뒤에서부터 앞에까지 숫자만큼 돌리기를 동시에 할 수 있는 방법을 모르겠다.
function solution(numbers) {// 17
const numString = numbers.toString();
let realNumbers = ""; // "17"
let arrNum = []; ["1","7"]
(let i = 0; i < numString.length; i++){
realNumbers += (numString[i]); //만약 17이면
arrNum.push(numString[i]);
}
if(realNumber % 2 != 0){
//만들 수 있는 조합 1,7,17,71 = [0],[1],[0+1],[1+0]
//이걸 어떻게 만들어야할지 모르겠다..
}
}//토끼님과 풀어따~!~!
//1.소수판별 이해 -> 2.set함수 이해 -> 3.getPermutations이해!
//4.filter함수로 함수 사용하기
//5.concat사용
function solution(numbers) {
const numString = numbers.toString();
let arrNum = [...numString];
let candidates = [];
//candidates를 flat.map으로 구현하는법 나중에 토끼님께 질문!
for(let i=1; i<=arrNum.length; i++) {
const result = getPermutations(arrNum, i);
candidates = candidates.concat(result);
}
const uniqueArr = [...new Set(candidates.map(arr=>parseInt(arr.join(""))))];
console.log(uniqueArr.filter(isPrime));
return uniqueArr.filter(isPrime).length;
//isPrime이라는 함수를 사용해서 filterArr에 있는 배열 요소들을 filter을 해서
//그 길이를 반환한다.
}
//길이 1이상 7이하인 문자열이라면 다중 for문을 7번 반복하지 않고
//어떻게 풀 수 있을까?
const getPermutations = function (arrNum, selectNumber) {
const combination = [];
if (selectNumber === 1) return arrNum.map((value) => [value]); // 1개씩 택할 때, 바로 모든 배열의 원소 return
arrNum.forEach((fixed, index, origin) => {
const rest = [...origin.slice(0, index), ...origin.slice(index+1)] // 해당하는 fixed를 제외한 나머지 배열
const permutations = getPermutations(rest, selectNumber - 1); // 나머지에 대해 순열을 구한다.
const attached = permutations.map((permutation) => [fixed, ...permutation]);
// 돌아온 순열에 대해 떼 놓은(fixed)값 붙이기
combination.push(...attached); // 배열 spread syntax 로 모두다 push
});
return combination;// 결과 담긴 combination return
};
function isPrime(n){
if(n <= 1) return false;
if(n === 2) return true;
for(let i = 2; i <= Math.floor(Math.sqrt(n)); i++){
if(n % i === 0) return false;
}
return true;
}관련 개념
- set 함수 : 배열안에 중복되는 요소를 없애주는 함수
- hash 함수 : 항상 같은 값을 꺼내주는 함수
- 소수 판별 :루트6이하의 합으로 나눠서 안나눠지면 소수임? 뭐 그런.. 더 알아보기.
- sqrt 함수: 루트를 씌워주는 함수
- 에라토스테네스의 체
https://ko.khanacademy.org/computing/computer-science/cryptography/comp-number-theory/v/sieve-of-eratosthenes-prime-adventure-part-4 - 다중 for문
const numArr = [1,2,3];
for(let i=0; i<numArr.length; i++) {
for(let j=0; j<numArr.length; j++) {
console.log(numArr[i], numArr[j])
}
}-
너무 적은 개수면 n^3이어도 충분히 빠르다
n의 개수가 50개 이하라서
너무 적은 개수면 n^3이어도 충분히 빠르다 -
소수 찾기
"127"
function permute(s, n){ // s를 고를 문자열, n은 몇 개를 고를지? "17"
if (n === 1){ // 1개를 고르면
return new Set([...s]); // set('1', '7')
}
const result = new Set();
for (let i = 0; i < s.length; i++){
const character = s[i]; // 글자를 하나 고르고
for (const result of permute(s.slice(0, i) + s.slice(i+1), n-1)){
result.add(character + result)
}
}
return result
}
function isPrime(num){
if(num === 2) return true;
for(let i = 2; i <= Math.floor(Math.sqrt(num)); i++){
if(num % i === 0) return false;
}
return true;
}
function solution(numbers) {
const result = new Set()
for (let i = 1; i <= numbers.length; i++){
for (const e of permute(numbers, i)){
result.add(parseInt(e));
}
}
return [...result].filter(n => n>1 && isPrime(n)).length;
}
프론트엔드 개발자를 꿈꾸는 개발초보 호랑이