[JavaScript] 소수 찾기 - 완전탐색

프로그래머스 - 알고리즘 고득점 Kit 완전탐색 편

 

완전탐색 세 번째 문제입니다.

소수 찾기 - 완전탐색

 

 

function solution(numbers) {
    const numArr = numbers.split('');
    const set = new Set();
    
    
    // 소수인지 확인하는 로직
    function isPrime(num) {
        if(num < 2) return false;
        for(let i = 2;i < Math.sqrt(num);i++) {
            if(num % 2 === 0) return false;
        }
        return true;
    }
    
    // 돌아가면서 숫자 경우를 생성하는 로직
    function makeNum(number, used) {
        if(number.length > 0) set.add(Number(number));
        
        for(let i = 0;i < numArr.length;i++) {
            if(!used[i]) {
                const newUsed = [...used];
                newUsed[i] = true;
                makeNum(number + numArr[i], newUsed);
            }
        }
    }
    
    makeNum('', Array(numArr.length).fill(false));
    
    // 소수만 남기기
    const primeArr = Array.from(set).filter(isPrime);
    
    return primeArr.length;
}

 

이전 완전탐색 문제들과 달리 필요한 작업이 많았습니다.

경우도 많기 때문에 재귀를 사용해서 구현했습니다.

 

1. 어떤 수를 사용했고, 사용하지 않았는지도 중요했습니다. used를 매개변수로 사용하여 사용여부를 판단했습니다.

 

2. for문을 돌면서 사용되지 않은 수인 경우에 + 연산을 이용해서 문자열을 붙이는 작업을 진행했습니다.

 

3. 소수인지 확인하는 로직에서는 

    2 이하의 수는 false, 제곱근을 이용하여 시간복잡도를 줄이고, 2로 나눈 나머지가 0인 경우에도 false를 줬습니다.

    모두 통과한 자들만 true를 줬습니다.

 

4. set을 배열(primeArr)로 만들고 isPrime인 수들만 filter를 하는 과정을 거쳤습니다. 

 

5. 남는 녀석들의 길이가 정답입니다.

 

 

 

다음 시간에도 완전탐색 네 번째 문제로 찾아뵙겠습니다~