Level2. 프로그래머스 소수찾기 - JavaScript

 

방법 1.

1. numbers에서 만들어질 수 있는 모든 경우의 수 구하기

2. 에라토스테네스의 체에서 소수가 맞는지 확인하기

 

처음에는 이렇게 생각했는데 모든 경우의 수를 구하는게 쉽지 않았다. 

 

따라서 다른 분의 방법을 참고하였다.

 

방법 2.

1. numbers의 수들을 내림차순으로 정렬한다

2. 에라토스테네스의 체를 확인하면서 소수인 수를 numbers와 비교한다.

 

좀 더 자세히 얘기하자면

방법 2 - 1 설명

numbers의 수가 "123"이라면 내림차순으로 정렬할 경우 321이 된다. 123이 가질 수 있는 모든 경우의 수 중에서 321보다 큰 경우는 없다.

다만 numbers는 0~9까지 이기 때문에 가능하다.

만약 numbers에 10이상의 수가 오게 된다고 가정하면

numbers의 수가 9103일때 가장 큰 수는 9310이지만 내림차순으로 정렬할 경우 1093이 된다.

 

즉 내림차순으로 정렬한 수가 가장 큰 수가 된다고 기대할 수 있다. 

 

function solution(numbers) {
    var answer = 0;
    // numbers를 배열로 변환하고 내림차순으로 정렬
    let a = numbers.split('').sort((a,b)=>b-a);
    // 최댓값
    let N = Number(a.join(''));
    // 에라토스 테네스의 체로 소수 구하기
    let arr = makePrimeNum(N);
    
    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;
}