[JavaScript][Programmers] 소수찾기

조준형·2021년 7월 15일

JavaScript level2 알고리즘 프로그래머스

Algorithm

목록 보기

34/142

🔎 소수찾기

❓ 문제링크

https://programmers.co.kr/learn/courses/30/lessons/42839

📄 제출 코드

function solution(numbers) {
    var answer = 0;

    var n = numbers.split('');
    var nums = new Set()
    // console.log(nums);

    combi(n, '');
    
    function combi(a, s) {
        if (s.length > 0) {
            // console.log(`s : ${s}`);
            if (nums.has(Number(s))=== false) {
                nums.add(Number(s));
                // console.log(Number(s))
                if (chkPrime(Number(s))) {
                    answer++;
                }
            }
            // console.log(nums);
            // console.log();
        }
        if (a.length > 0) {
            for (var i = 0; i< a.length; i++) {
                var t = a.slice(0)
                // console.log(`before t : ${t}`)
                t.splice(i,1);
                // console.log(`after t : ${t}`)
                combi(t, s + a[i]);
                
            }
        }
    }

    function chkPrime(num) {
        if (num < 2) return false;
        if (num === 2) return true;
        for (var i = 2; i < num; i++) {
            if (num%i===0) return false;
        }
        return true;
    }

    return answer;
}
let numbers = "17";
console.log(solution(numbers));

처음에 조합을 구해서, 소수인지 검사해서 answer을 ++하면되겠다했는데, 구현이 잘 안됐다.
그래서 다른사람의 풀이를 보고 이해하려고 하였다.

먼저 조합은 numbers배열을 내림차순으로 정렬한것과, 빈배열로 시작한다.
내림차순 한 이유는 n이 0~9이기 때문에 정렬 시 가장 큰 수가 보장되기 때문이다.
numbers의 수가 "123"이라면 내림차순으로 정렬할 경우 321이 된다. 123이 가질 수 있는 모든 경우의 수 중에서 321보다 큰 경우는 없다.

조합은 t에 넘어오는 배열을 복사하여 t의 첫번째 배열을 떼내서 s에 붙인다.
그럼 s에서 nums에 s가 있는지 검사하여 없으면, nums에 추가하고, 만약 소수검사를 했을 때 true라면, answer++해서 답을 도출한다.

소수검사는 넘어온 숫자가 2보다 작으면 false => 0과 1은 소수가 아니다.
2는 짝수지만 소수이기 때문에 true를 리턴.
그 다음 2부터 숫자의 제곱근 만큼 반복하면서 num이 i로 나눳을 때 0이있으면 false 아니면, true를 리턴해서 소수를 확인한다.

처음에 소수 판별할 때 num-1까지 검사 해봐야 되는거 아닌가? 라고 생각해서

for (var i = 2; i < num; i++) {
  if (num%i===0) return false;
}

이렇게 제출했었는데 일단 통과는 됐다.
근데 왜 사람들이 제곱근 까지만 하는 지 찾아보았다.

👉 제곱근

N의 약수는 무조건 sqrt(N)의 범위에 존재한다.

만약 N이 12라 할때, 12의 제곱근은 약 3.46이다.
12의 약수는 1, 2, 3, 4, 6, 12 이다.
여기서 1과 12를 제외했을 때 이는 2 6, 3 4, 4 3, 6 2의 결과이다.

이들의 관계는 몫이 커지면 나누는 값이 작아지거나 나누는 값이 커지만 몫이 작아지는 반비례 관계이다. 결국 N의 절반(제곱근)까지 향하게 되면 이후 몫과 나누는 값이 반대로 바뀌게만 되는 상황이다.

따라서 N의 제곱근까지 나누어 떨어지는지 여부를 조사하면 더 빠르게 소수판별을 할 수 있다.
하나 배워간다.

🎲 다른 코드

function solution(numbers) {
    var answer = 0;
    // numbers를 배열로 변환하고 내림차순으로 정렬
    let a = numbers.split('').sort((a, b) => b - a);
    // let a = numbers.split('');
    console.log(a);
    // 최댓값 
    let N = Number(a.join(''));
    // 에라토스 테네스의 체로 소수 구하기 
    let arr = makePrimeNum(N);
    console.log(arr);
    
    for (let i = 2; i <= N; i++){
        // 소수가 아니면 패스 
        if (arr[i] == false) continue;
        // 소수면 해당 숫자를 문자열로 바꾸고 배열로 변환 
        let temp = i.toString().split('');
        // numbers에 해당 하는 값을 돌면서 temp에도 있으면 temp에서 삭제 
        for (let cn of a) {
            let idx = temp.indexOf(cn);
            if (idx > -1) temp.splice(idx, 1);
        }
        // temp.length가 0이면 numbers에 모두 있는 숫자 이므로 answer++
        if (temp.length == 0) answer++;
    } return answer;
} //에라토스테네스의 체 
function makePrimeNum(N) {
    let arr = [];
    for (let i = 2; i <= N; i++){
        if (arr[i] == false) continue;
        for (let k = i + i; k <= N; k += i){
            arr[k] = false;
        }
    } return arr;
}
let numbers = "17"
console.log(solution(numbers))