[프로그래머스] 완전 탐색 - 소수 찾기

2021_11_07 알고리즘 스터디 

문제 URL : https://programmers.co.kr/learn/courses/30/lessons/42839?language=javascript 

코딩테스트 연습 - 소수 찾기

문제

 

풀이

function solution(numbers) {
    const result = [];
    const validMaxNum = numbers.split("").sort((a, b) => parseInt(b) - parseInt(a)).map((num)  => String(num)).join("");
    
    let i = 2;
    while (i <= validMaxNum) {
        if (isPrime(i)) {
            result.push(i)
        }
        i++;
    }
    
    return result.filter((ite) => {
        let duplicatedNumbers = [...numbers];
        const splitedPrime = String(ite).split("");

        for (let j = 0; j < splitedPrime.length; j++) {
            const index = duplicatedNumbers.findIndex((nu) => nu === splitedPrime[j]);
                
            if (index > -1) {
                duplicatedNumbers = duplicatedNumbers.slice(0, index).concat(duplicatedNumbers.slice(index +1));
            } else {
                return false;
            }
        }
        return true
    }).length;
}

function isPrime(num) {
    let i = 2;
    
    while (num > i) {
        if (num % i === 0) return false;
        i++;
    }
    return true;
}

채점

O(n^2) 코드로 채점을 진행했을 때, 시간 초과가 뜨는 것을 볼 수 있었고, 시간 복잡도 해결을 위해 다시 고민을 했다.

 

function isPrime(num) {
    let i = 2;
    
    while (num > i) {
        if (num % i === 0) return false;
        i++;
    }
    return true;
}

function solution(numbers) {
    const answer = new Set();
    let nums = numbers.split(''); 
    
    const getPermutation = (arr, fixed) => {
        if(arr.length > 0) {
            for (let i=0; i<arr.length; i++) {
                const newFixed = fixed + arr[i];
                // 고정값에 배열의 i번째 요소를 합쳐 새로운 고정값으로 지정
                
                const copyArr = arr.slice();
                copyArr.splice(i, 1);
                // newFixed로 고정한 요소를 배열에서 제거하여, 고정되지 않은 요소들로 배열을 채운다.
                // 도출된 조합이 answer에 들어있지 않고, 소수일 경우 answer에 추가하도록 하였다.
                if (!answer.has(parseInt(newFixed)) && isPrimeNum(parseInt(newFixed))){
                    answer.add(parseInt(newFixed)) //newFixed 조합을 answer에 추가
                }
                getPermutation(copyArr, newFixed);
                // 고정되지 않은 요소들이 담긴 배열과, 새로운 고정값을 인자로 전달하여 getPermutation 호출.
            }
        }
    }
    getPermutation(nums, '');
    return answer.size;
}