[Programmers/javascript] 소수 찾기

1. 문제

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

제한사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

2. 풀이

해당 문자열로 생성할 수 있는 모든 숫자들을 생성하여 집합(Set)에 저장한다.(중복을 제거하기 위해)
마무리로 소수인 수의 갯수를 구하고 반환한다.

function solution(numbers) {
    var answer = 0;
    var n = numbers.split('');
    var nums = new Set();
    permutation(n, '');

    function permutation(a, s) {
        if (s.length > 0) {
            if (!nums.has(Number(s))) {
                nums.add(Number(s));
                // console.log(Number(s));
                if (isPrime(Number(s))) {
                    answer++;
                }
            }
        }
        if (a.length > 0) {
            for (var i = 0; i < a.length; i++) {
                var t = a.slice(0);
                t.splice(i, 1);
                // console.log(t, s + a[i]);
                permutation(t, s + a[i]);
            }
        }
    }

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

[참조]

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

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