[JS] 소수 찾기

순열을 구하는 함수와 소수임을 판별하는 함수를 하나씩 구한 이후, 완전탐색으로 구했다.

 

 

1. 함수 이름을 조합으로 했는데 생각해보니 순서에 따라서 숫자가 달라질 수 있으므로 순열을 구하는게 맞는거 같아서 중간에 수정을 해주었다.

 

2. 소수인지 아닌지 판별하는 isPrime() 함수를 생성

 

3. 완전탐색으로 소수인 수들을 넣는데 011과 11의 경우 같은 수로 생각하므로 둘을 숫자로 바꾼 이후, Set 자료형을 활용해서 중복을 없애주는 형식으로 구현하였다.

 

4. Set의 size를 반환하면서 마무리

 

 

약간 복잡한 알고리즘이 들어간다기 보다는 3가지 정도의 문제가 합쳐진 듯한 문제였다.

 

 

 

const getCombination = (arr,n) => {
    let ret = []
    if (n===1) return arr.map(v =>[v])
    
    arr.forEach((fixed,idx,arr) => {
        
        const rest = [ ...arr.slice(0,idx), ...arr.slice(idx+1)]
        getCombination(rest,n-1).forEach(el => ret.push([fixed , ...el]))
    })
    return ret
}

const isPrime = (n) => {
    if (n<2) return false
    for (let i = 2 ; i <= n**0.5 ; i++) {
        if (!(n%i)) return false
    }
    return true
}
 
function solution(numbers) {
    let ret = new Set()
    const numList = numbers.split("")
    
    for (let i = 1 ; i <= numbers.length ; i++){
        const combi = getCombination(numList,i)
        for (const num of combi) {
            const n = ~~num.join("")
            if (isPrime(n)) ret.add(n)
        }
    }
    return ret.size
}