[프로그래머스] 소수찾기 (Level 2) - javascript

📝 문제

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

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

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

👌 선수 개념

위 문제를 풀기 위해서는 조합과 순열 개념과 이를 js로 구현하는 방법을 알아야 한다.
내용이 방대해서 따로 포스팅으로 정리했다.
 
[알고리즘] 순열과 조합 - javascript
 
이를 이해했다면 문제를 풀 수 있다.
 

🔑 풀이

function solution(numbers) {

    numbers = numbers.split('');

    function isPrime(num) { // 소수 판별 함수
        if(num <= 1) return false;
        for(let i = 2; i*i <= num; i++) {
            if(num % i === 0) return false;
        }
        return true;
    }

    function permutation(arr, selectNum) { // 순열 함수

        let result = [];
        if(selectNum === 1) return arr.map(v => [v]);

        arr.forEach((v, idx, arr) => {
            let fixed = v;
            let restArr = arr.filter((e, index) => index !== idx);
            let restPermutations = permutation(restArr, selectNum - 1);
            let combineArr = restPermutations.map(e => [fixed, ...e]);
            result.push(...combineArr);
        })
        return result;
    }

    let set = new Set(); // 중복을 걸러줄 set 생성 (011, 11은 같음)
    
    for(let i = 1; i <= numbers.length; i++) { // 고르는 숫자 갯수
        let selectNums = permutation(numbers, i);
        selectNums.forEach(arr => { // [[1,2], [2,1]] 이런 형태로 주어짐
            let selectNum = +arr.join(''); // 문자열로 만들고, 숫자로 변환
            if(isPrime(selectNum)) set.add(selectNum); // 소수면 set에 추가
        })
    }

    return set.size;
}

 

• 정확도 테스트 결과