프로그래머스 소수 찾기 - level2 (완전 탐색)

오늘은 프로그래머스 소수 찾기 문제를 풀어보겠습니다.

문제는 다음과 같습니다.

 

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

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

 

이 문제는 전형적인 완전 탐색입니다.

numbers이라는 문자열이 주어지고, 문자열 내에 모든 소수의 경우를 찾아서 개수를 출력하면 됩니다.

 

알고리즘은 다음과 같습니다. 

1. dfs 방식으로 모든 경우의 수를 찾습니다. 

const getNumbers = (current, str) => {
        if(current === len + 1) return;
        if(getPrime(+str)) answer.add(+str);
        for(let index = 0; index < len; index++) {
            if(visited[index])continue;
            visited[index] = 1;
            getNumbers(current+1, str + numbers[index]);
            visited[index] = 0;
        }
    }

 

2. 소수 알고리즘  - 2이거나 약수가 1과 자신뿐이면 소수이고, 아니면 소수가 아님.

 const getPrime = (number) => {
        if([0,1].includes(number)) return false;
        if(number === 2) return true;
        for(let index = 2; index < number; index++) {
            if(number % index === 0)return false;
        }
        return true; 
   }