[프로그래머스] 완전탐색 - 소수 찾기 (javascript)

문제 설명 

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

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

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

numbers	return
"17"	3
"011"	2

입출력 예 설명
예제 #1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

예제 #2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

11과 011은 같은 숫자로 취급합니다.

 

---

현재 코딩 테스트를 준비하기 위해 다양한 알고리즘 문제를 접하고 있었다. 이 문제는 완전탐색 문제중 하나였는데 아무런 지식이 없는채로 문제를 푸려고 하니 풀리지가 않았다. 따라서 다른 분들이 푼 것을 참고하여 완전히 이해하고 작성한다. 

 

나의 풀이 

function solution(numbers) {
    var answer = new Set();
    let arr = [];
    
    for(let i of numbers){
        arr.push(i);
    }

    function isPrime(N) {
        if (N === 1 || N === 0) return false;
        for (let i = 2; i <= Math.sqrt(N); i++) {
            if (N % i === 0) return false;
    }
    return true;
    }
    function getPermutation(arr, fixed){
        if(arr.length >= 1){
            for(let i = 0; i<arr.length ; i++){
                let newFixed = fixed + arr[i]; // 문자열 더하는 것임 
                const newArr = arr.slice() ; // 
                newArr.splice(i,1); // 고정한 요소를 제거한 배열 
                if(!answer.has(parseInt(newFixed)) && isPrime(parseInt(newFixed))){
                    answer.add(parseInt(newFixed));
                }
                getPermutation(newArr, newFixed);
            }
        }
    }
    getPermutation(arr,'');
    
    return answer.size;
}

주어진 문자열로 조합할 수 있는 숫자 중 소수인 것의 갯수를 구하는 문제이다. 이 문제는 완전탐색으로 가능한 모든 조합을 만들어내야했다. 따라서 먼저 문자열로 주어진 것을 각각 하나씩 나누기 위해 for of 문을 사용하여 새롭게 선언한 arr에 할당해주었다. 따라서 '17' 로 주어진 문자열은 arr에 ['1' ,'7'] 형식으로 저장할 수 있었다. 또한 answer은 Set으로 선언해주었다. 이는 중복 요소를 제거하기 위함이다. 

 소수 판별을 위한 함수인 isPrime을 선언해주었다. 소수는 그 수의 제곱근 이하 까지만 판별해서 나누어지는게 없으면 true 를 리턴하게 작성하였다. 물론 0과 1 일때는 소수가 아니므로 그 경우는 제외해주었다. 

완전 탐색을 위한 함수인 getPermutation 함수는 인자로 배열과 고정 요소를 가지며 재귀함수이다. 
간단하게 설명하자면 고정된 요소를 제외하고 나머지 요소들을 조합하여 고정된 요소에  합치고를 반복하는 것이다. 
for문내에서는 새로운 고정 요소인 newFixed 변수를 선언해 기존의 고정된 요소에 합쳐준다. 자바스크립트의 특성상 문자열 + 문자열은 문자열이므로 '1' + '7' 은 '17' 이될것이다. '8' 이라고 혼동하면 안된다. 
그 후 기존의 배열을 건드리지 않고 새로운 배열을 생성하기 위해 slice로 newArr를 선언해주었고  splice로 고정한 요소를 제거한 배열로 만들어주었다. 
그 후 if문으로 중복된 값이 아니고 소수일 때 정답 배열에 추가해주었다. 또한 재귀적으로 함수를 호출하기 위해 함수를 호출해주었다. 

함수의 바깥에는 함수를 처음 시작하기 위해 호출해주었고 소수의 갯수를 구하는 것이므로 answer.size로 리턴해주었다.  Set 은 배열과 다르게 길이를 구할 때 size를 사용한다는 것을 혼동하면 안된다. 

위의 짠 코드를 바탕으로 실제 예시를 가지고 실행해본다고 가정하면 
numbers가 '17'로 주어졌다고 가정해보자 
1. '17'은 for of문에 의해 arr = ['1','7'] 이 된다 
2. getPermutation(arr,''); 이 실행된다. 
3. arr.length 는 2이므로 for문이 실행된다. 
4. newFixed = '' + '1' ; 이므로 newFixed는 '1' 이된다. 
5. newArr = ['1', '7'] 이다. 
6. newArr.splice(i,1)  i는 0이므로 0번째 요소를 제거한다. 즉 newArr는 ['7']이 된다. 
7. if문 내의 조건인 첫번째 조건은 만족하지만 1은 소수가 아니므로 answer에 추가되지 못한다. 
8. getPermutation('7','1'); 이 실행된다. 
9. newFixed = '1' + '7' 이 되므로 newFixed는 '17'
10 . newArr.splice(i,1)은 '' 이다. 
11. 17은 소수이고 answer에 없기 때문에 answer에 추가된다. 
12. getPermutation('' , '17')이 실행된다. 
13. arr의 길이가 '' 이므로 if문 내부가 실행되지 않고 함수가 종료된다. 
14. 바로 전 호출된 함수로 돌아가고 , for문을 모두 돌았기 때문에 종료하고 그 전 함수로 돌아간다. 
15. 가장 첫번째로 호출됐던 함수로 돌아가고 for문의 i=1이 되고 newFixed = " +'7' 이므로 '7'이된다. 
16. newArr는 ['1']이 된다. 
17. 7은 if문의 조건을 모두 만족하므로 answer에 추가된다. 
18. getPermutation('1' , '7');이 실행된다. 
19. newFixed = '7'+'1' = '71' 
20. 71은 소수이고 answer에 없기 때문에 answer에 추가된다. 
21. getPermutation (", '71') 이 실행된다. 
22. if문 내부가 실행되지 않고 함수가 종료된다. 
23. 바로 전 함수로 돌아가고 for문을 모두 돌았기 때문에 종료하고 그 전함수로 돌아간다. 
24. 그 전 처음에 실행한 함수도  for문을 모두 돌았기 때문에 종료하며 마지막으로 answer에는 7, 17, 71이 들어가있으며 size는 3 즉 3이 리턴되며 종료된다. 

함수의 모든 실행과정을 작성해보았다. 
이제 순열문제가 나오면 혼동하지 않고 잘 풀 수 있을 것 같다 !