소수찾기 (level2)

주어진 숫자 조각을 조합해 소수가 몇 개인지 return하는 solution 함수를 완성하자

풀이

1. 문자열로 입력되는 숫자 조각으로 만들 수 있는 수를 배열에 저장한다.

2. 소수인지 판별한다.

숫자 조각

    const number = 
            numbers
              .split("")
              .map(a => parseInt(a))

순열

숫자 조각들을 사용해 만들 수 있는 모든 경우를 구하기 위해서 순열알고리즘을 사용해야한다.

순열이란

서로 다른 n개의 물건 중에서 r 개를 택해 한 줄로 배열하는 것을 의미한다.

순열은 재귀함수를 통해 구할 수 있다.

원리는 이렇다.

const arr = [1, 2, 3, 4]에서 하나를 fixed 하고 나머지 원소들로 순열 만드는 것이다.

	const getP = (arr, selectNumber) => {
    	const result = []
        if(selectNumber === 1) return arr.map(el => [el])
      	// 원소 중 하나를 뽑는건 의미가 없기 때문에 그냥 배열로 리턴한다.
      
      arr.forEach((fixed, index, origin) => {
      	const rest = [...origin.slice(0, index), ...origin.slice(index+1)]
        // fixed 외 배열
        const p = getP(rest, selectNumber-1)
        // 나머지 순열 구하기
        const attached = p.map(el => [fixed, ...el])
        // p를 fixed에 붙이기
        result.push(...attached)
      })
      return result
    }

소수판별

소수판별은 에라토스테네스의 체를 이용하면 쉽게 판별할 수 있다.

하지만 해당 문제는 큰수를 판별하는 것이 아니기 때문에 단순 연산을 통해 구할 수 있다.

코드

function findPrime(num) {
    if(num === 0 || num === 1) return false
    else if(num === 2 || num === 3) return true
    for(let i = 2; i <= num/2; i++){
        if(num%i === 0) return false
    }
    return true
}
function getP(arr, selectNumber){
    	const result = []
        // if(selectNumber === 1) return arr.map((el) => [el])
      
      arr.forEach((fixed, index, origin) => {
      	const rest = [...origin.slice(0, index), ...origin.slice(index+1)]
        const p = getP(rest, selectNumber-1)
        const attached = p.map(el => [fixed, ...el])
        result.push(...attached)
      })
      return result
}



function solution(numbers) {
    var answer = 0;
    const number = numbers.split("")
    let num = []
    for(let i = 1; i < numbers.length; i++){
            let final = getP(numbers, i)
            num.push(...final)
    }
    let set = [...new Set(num.flatMap(el => Number(el.join(""))))]
    for(const item of set){
        if(findPrime(item)) answer++
    }
    return answer;
}