Programmers 소수 찾기 2단계

문제

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

제한 사항

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

입출력 예 설명

예제 #1

• [1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

예제 #2

• [0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.
  11과 011은 같은 숫자로 취급합니다.

풀이

function solution(numbers) {
	let result = [];
    let nums = numbers.split("");
    
    function isPrime(num) {
		for(let i = 2; num > i; i++) {
  			if(num % i === 0) {
    			return false;
   			}
  		}
		return num > 1;
	}
    
    // 순열을 통해 각 숫자를 모두 조립해봐야 한다.
    function getPermutation (arr, fixed) {
    	if(arr.length >= 1){
        	for(let i = 0; i < arr.length; i++){
            	let newNum = fixed + arr[i];
                let copyArr = [...arr];
                copyArr.splice(i, 1);
                if(!result.includes(+newNum) && isPrime(+newNum)){
                	result.push(+newNum);
                }
                getPermutation(copyArr, newNum); 
            }
        }
    }
    getPermutation(nums, "");
    return result.length;
}

문제를 해결하면서 소수 찾기까지는 쉽게 생각해서 구현할 수 있었다. 각 숫자를 조립하기 위해서 반복문을 사용하려했으나, 비효율적이라 풀이 방법을 생각하기까지 오랜 시간이 걸렸다.
getPermutation 공식을 활용해 순열로 모든 조합 찾기를 할 수 있었고 조합된 newNum 앞에 +를 붙여서 전부 숫자로 변경 처리했다.

결론.. 소수 구하는 방법과 완전 탐색(순열)에 대해서 모르면 풀 수 없는 문제다.