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

문제 설명

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

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

제한사항

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

입출력 예

풀이

numberLog는 생성된 숫자를 저장하는 set 이고
isSelected은 숫자를 만들때의 사용유무를 저장하는 배열이다.
만든 숫자(String)과 isSelected와 생성된 숫자 길이를 파라미터로 makeNumber() 를 실행한다.
만약 count 값이 numbers.length 보다 크면 return 한다.
그렇지 않으면 선택되지 않은 숫자들을 붙여서 새로운 숫자를 만든다.
이를 숫자형으로 변경하고 이를 isPrimeNumber() 함수에 파라미터로 넣어 소수인지 확인한다.
만약 소수이면 answer 값을 1 증가 시킨다.
사용된 숫자를 사용처리해주고 함수를 재귀적으로 실행하여
반복한다.

function solution(numbers) {
    let answer = 0;
    let isSelected = Array(numbers.length).fill(false);
    let numberLog = new Set();
    numbers = numbers.split('');

    function checkPrimeNumber(number) {
        if (number < 2) return;

        let maxNumber = Math.floor(Math.sqrt(number));
        for (let i = 2; i <= maxNumber; i++) {
            if (number % i === 0)
                return;
        }
        answer++;
    }
    function makeNumber(numberString, isSelected, count) {
        if (count > numbers.length) return;

        for (let i = 0; i < numbers.length; i++) {
            if (!isSelected[i]) {
                let newNumber = Number(numberString + numbers[i]);

                if (!numberLog.has(newNumber)) {
                    numberLog.add(newNumber);

                   checkPrimeNumber(Number(newNumber));
                }

                let newIsSelected = [...isSelected];
                newIsSelected[i] = true;
                makeNumber(numberString + numbers[i], newIsSelected, count + 1);
            }
        }
    }

    makeNumber("", isSelected, 0);
    return answer;
}