[프로그래머스/JavaScript] 소수 찾기

문제

한 자리 숫자가 적힌 종이 조각이 흩어져 있다. 흩어진 종이 조각을 붙여 몇 개의 소수를 만들 수 있는 지 알고 싶다.

각 종이 조각을 붙인 문자열 `numbers`가 주어진다.

• 1 ≤  `numbers` ≤ 7

 

풀이

`numbers`의 길이 범위가 1~7인 것으로 보아, 완전 탐색을 사용해도 성능 상 무리가 없다는 것을 알 수 있다.
순열의 경우, n개의 원소로 만들 수 있는 모든 경우의 수는 n!이며, 일반적으로 n ≤ 7~8일 때는 완전 탐색(브루트포스)이 안정적으로 동작한다.
예를 들어, n = 7이라면 7! = 5040개의 조합이 생성되며, 이는 1초 내에 충분히 탐색 가능한 수준이다.

다만 9 이상이 되면 경우의 수가 급격히 증가(9! = 362,880)하기 때문에 이 경우에는 백트래킹, 가지치기, DP 등의 최적화 기법이 요구된다.

 

`getCombinations`는 `path` 배열의 길이 0 이상이면 `result` `Set`에 경우의 수를 담는다. 만일 종이 조각의 숫자가 중복될 경우 중복된 숫자가 만들어질 수 있으므로 `Set`을 사용한다.

 

만들어진 숫자들을 소수 판별한 뒤 카운트해준다.

 

코드

function solution(numbers) {
    const result = new Set();
    const visited = Array(numbers.length).fill(false);
    
    function getCombinations(path) {
        if (path.length > 0) {
            result.add(Number(path.join("")));
        }
        for (let i = 0; i < numbers.length; i++) {
            if (visited[i]) continue;
            visited[i] = true;
            path.push(numbers[i]);
            getCombinations(path);
            path.pop(numbers[i]);
            visited[i] = false;
        }
    }
    
    getCombinations([]);
    
    let count = 0;
    for (const num of result) {
        if (isPrime(num)) {
            count++;
        }
    }
    return count;
}

function isPrime(num) {
    if (num < 2) return false;
    for (let i = 2; i <= Math.sqrt(num); i++) {
        if (num % i === 0) return false;
    }
    return true;
}