[programmers] 완전탐색 - 소수 찾기

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

문제

문제 설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 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은 같은 숫자로 취급합니다.

사고방식

1. 모든 경우의 수를 추출

=> 순서를 중요시하는 순열을 사용해야겠다고 생각했습니다.

파이썬으로 순열을 설명한 유튜브 영상입니다. 이해가 잘되서 순열 알고리즘이 이해가 안가신다면 보시는 걸 추천드립니다.

www.youtube.com/watch?v=6E69_ddpBwU

2. 그 경우의 수에서 소수추출

medium.com/@hyunhodl/%EC%86%8C%EC%88%98-%ED%8C%90%EB%B3%84-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-with-%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8-eef9007b290f

소수를 판별하는 함수를 따로 만들고자 소수를 구하는 방법에 대해 고민해보았습니다. 소수는 나누어 나머지가 0 이 되는 값이 1과 자기자신의 수만 존재하는 것을 말합니다.

처음에는 1부터 그 해당 수까지 모두 나눠서 배열에 추가해주고 그 배열의 길이가 2개 이면 소수라고 판단하였으나, 검사량이 많다고 생각하여, 소수를 구하는 과정에서 해당 수의 반복되는 경우를 파악하였습니다.

예를 들어 24가 소수인지 아닌지 판별해보겠습니다.

==========================

24 = 2 * 12
24 = 3 * 8
24 = 4 * 6
24 = 6 * 4
24 = 8 * 3
24 = 12 * 2

==========================

이 과정에서

==========================

24 = 2 * 12
24 = 3 * 8
24 = 4 * 6

==========================

과

==========================

24 = 6 * 4
24 = 8 * 3
24 = 12 * 2

==========================

는 정확히 대칭입니다.

즉, 2, 3, 4 로만 나누어보아도 이게 6, 8, 12 로 나누어질지 아닐지가 판단이 가능하다는 의미입니다.

그렇기 때문에 주어진 숫자의 제곱근 이하까지만 나우어봐도 소수인지 아닌지 판별할 수 있습니다.

 

3. result 값의 길이를 출력

해결코드 [javascript]

function solution(numbers) {
    var answer = 0;
    let result = [];
    let results = [];
    const arrNum = numbers.split('');
    const checklist = Array.from({length: arrNum.length}, () => 0);
    for(let i=1; i<=arrNum.length; i++){
        DFS(0, i);
    }
    
    // 소수인지 아닌지 판별하는 함수
    function isPrime(n) {
        if (n <= 1) {
            return false;
        }
        if (n === 2 || n === 3) {
            return true;
        }
        if (n % 2 === 0) {
            return false; 
        }
        let divisor = 3;
        let limit = Math.sqrt(n);
        while (limit >= divisor) {
            if (n % divisor === 0) {
                return false;
            }
            divisor += 2;
        }
        return true;
    }
    
    // 모든 순열의 조합을 찾는 함수
    function DFS(n, r){
        if(n == r) {
        	// 중복되는 값은 패스하고 소수만 추가
            if(!results.includes(parseInt(result.join(''))) && isPrime(parseInt(result.join('')))){
                results.push(parseInt(result.join('')));
            }
        } else{
            for(let i=0; i<arrNum.length; i++){
                if(checklist[i] == 0){
                    result[n] = arrNum[i];
                    checklist[i] =1;
                    DFS(n+1, r);
                    checklist[i] =0;
                }
            }
        }
    }
    answer = results.length;
    return answer;
}