[Javascript] 소수 찾기

🧾 목차

1. 문제 설명

2. 문제 풀이

3. 정답 코드

---

1. 문제 설명

나올 수 있는 모든 수의 조합을 구하여, 소수의 개수를 리턴하는 문제이다.

 

입출력 예제

 

제한사항

- 1 <= numbers.length <= 7

- 중복 가능 (e.g. "011")

2. 문제 풀이

 

가능한 모든 조합을 구하여, 소수인 경우에만 리스트에 넣어주면 된다.

 

1) 이 때, 만들 수 있는 소수 리스트는 중복을 배제해야한다.

e.g. "001", "01" 은 모두 숫자 1로 해석된다는 의미

 

    var primeNumbers = new Set(); // 만들 수 있는 모든 소수 리스트 (중복 x)
    var len = numbers.length; // 입력 문자열의 길이

 

 

2) 소수 판별 함수 구현

- 수가 0 또는 1인 경우, 반드시 소수가 아님

- 2부터 ~ 제곱근 까지 반복하여, 해당 수로 나누어떨어지면 👉 소수가 아님

    // 소수 판별 함수
    function isPrime(n) {
        if (n == 0 || n == 1) {
            return false;
        }
        
        for (let i = 2; i <= Math.sqrt(n); i++) { // 제곱근까지
            if (n % i == 0) {
                return false;
            }
        }
        
        return true;
    }

 

3) 조합 함수를 구현한다.

백트래킹 알고리즘을 사용해서 구현했다.

 

⭐ 핵심

사용하지 않은 조각일 때, 재귀 함수를 호출한다. ( + 방문 표시 필수)

재귀 함수를 호출한다음, 반드시 방문 해제를 해줘야한다.

 

    // 조합 
    function combi(n, visited) {
        if (isPrime(+n)) { // 소수일 경우
            primeNumbers.add(+n); // 소수 리스트에 추가
        }
        
       
        for (let i = 0; i < len; i++) {
            if (!visited.has(i)) {  // 사용하지 않은 종이 조각이라면, 추가하기
                visited.add(i); 
                combi(n + numbers[i], visited); 
                visited.delete(i); // 백트래킹
            }
        }
    }
    
    combi('', new Set());

 

참고

문자열 옆에 '+' 는 문자열을 수로 변환하는 코드이다. 

a = '123'일 때, +a는 123

a = ''일 때, +a는 0

 

3. 정답 코드

function solution(numbers) {
    
    var primeNumbers = new Set(); // 만들 수 있는 모든 소수 리스트 (중복 x)
    var len = numbers.length;
    
    // 소수 판별 함수
    function isPrime(n) {
        if (n == 0 || n == 1) {
            return false;
        }
        
        for (let i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                return false;
            }
        }
        
        return true;
    }
    
    // 조합 
    function combi(n, visited) {
        if (isPrime(+n)) { // 소수일 경우
            primeNumbers.add(+n); // 소수 리스트에 추가
        }
        
       
        for (let i = 0; i < len; i++) {
            if (!visited.has(i)) {  // 사용하지 않은 종이 조각이라면, 추가하기
                visited.add(i); 
                combi(n + numbers[i], visited); 
                visited.delete(i); // 백트래킹
            }
        }
    }
    
    combi('', new Set());

    return primeNumbers.size;
}