프로그래머스 [JS] > 소수찾기

 

 

🔥문제링크

https://school.programmers.co.kr/learn/courses/30/lessons/42839

프로그래머스

 

 

🔥풀이

핵심은 재귀적으로 모든 순열을 구하는 프로세스 와 소수를 빠르게 찾는 프로세스이다.

처음에 재귀적으로 접근하면 시간에서 걸릴 것 같았는데 걸리지 않았고 오랜만에 재귀적 방법을 이용했어서 처음에는 풀이가 바로 생각나지 않았다.

function solution(numbers) {

    let primeNumbers =[]

    // dfs (깊이 우선 탐색 정의 )
    const dfs =(picked,unpicked,selectCount)=>{
        if(selectCount===1){
            unpicked.forEach((n)=>{
                primeNumbers.push(Number([...picked,n].join('')))
            })
            return 
        }
        unpicked.forEach((n,i,origin)=>{
            let newPick = [...picked,n]
            let newUnpicked = [...origin]
            newUnpicked.splice(i,1)
            dfs(newPick,newUnpicked,selectCount-1)
        })
    }
    
    // 길이가 1 ~ 문자열의 길이 만큼의 자릿수를 가지는 숫자를 도출함
    let count = 1  
    while(count<=numbers.length){
        dfs([],[...numbers],count)
        ++count
    }
    
    //중복 제거 
    primeNumbers = new Set([...primeNumbers])

    //소수만 찾는다
    let answerArr = Array.from(primeNumbers).filter((n)=>{
        let isPrimeNumber = true
        
        for(let i=2; i<=Math.sqrt(n); ++i){
            if(n%i===0){
                isPrimeNumber = false
            }
        }
        
        return ( n === 1 || n===0 || !isPrimeNumber ) ? false : true
    })
    
    

    return answerArr.length;
}