프로그래머스 k진수에서 소수 개수 구하기 - 자바스크립트 풀이

프로그래머스

437674을 3진수로 바꾸면 211020101011입니다. 여기서 찾을 수 있는 조건에 맞는 소수는 왼쪽부터 순서대로 211, 2, 11이 있으며, 총 3개입니다. (211, 2, 11을 k진법으로 보았을 때가 아닌, 10진법으로 보았을 때 소수여야 한다는 점에 주의합니다.) 211은 P0 형태에서 찾을 수 있으며, 2는 0P0에서, 11은 0P에서 찾을 수 있습니다.
정수 n과 k가 매개변수로 주어집니다. n을 k진수로 바꿨을 때, 변환된 수 안에서 찾을 수 있는 위 조건에 맞는 소수의 개수를 return 하도록 solution 함수를 완성해 주세요.

 

코드

function isPrime(num){
    let number = parseInt(num, 10);
    if(number < 2) return false;
    
    for(let i = 2; i * i <= number; i++){
        if(number % i === 0) return false;
    }
    return true;
}

function solution(n, k) {
    let converted = n.toString(k);
    let split = converted.split("0").filter(x => x.length > 0);
    return split.reduce((a,c) => a += isPrime(c) ,0);
}

 

간단 설명

소수인지 아닌지 판별하는 함수부터 작성해보자.

function isPrime(num){
    let number = parseInt(num, 10); // 10진수로 변환
    if(number < 2) return false;
    
    for(let i = 2; i * i <= number; i++){
        if(number % i === 0) return false; // 자기 자신, 1 이외에 나눠떨어지는 값이 있으면 소수가 X
    }
    return true;
}

우선 문제 조건에 따라 인자로 받아온 num 값을 10진수로 변환 후 소수인지 아닌지 판별해야하므로

let number = parseInt(num, 10);
if(number < 2) return false;

이와 같이 10진수로 변환해준 값을 number 변수에 할당한다. 이 때, 2보다 작은 1과 같은 수는 소수가 아니므로 바로 false를 반환해주자.

이제 소수인지 아닌지 판별해보자.

for(let i = 2; i * i <= number; i++){
	if(number % i === 0) return false;
}
return true;

자기 자신과 1을 제외한 값 중 나눠떨어지는 값이 있다면 false를 반환해주자. for문을 실행한 결과 나누어 떨어지는 값을 찾지 못했다면 소수인 것이므로 true를 반환하게된다.

이제 조건에 맞는 값을 찾아 개수를 구하자.

function solution(n, k) { // 예제: n = 437674, k = 3
    let converted = n.toString(k);
    let split = converted.split("0").filter(x => x.length > 0);
    return split.reduce((a,c) => a += isPrime(c) ,0);
}

우선 인자 n 값을 k진수로 변환하자.

let converted = n.toString(k); // 211020101011

이제 0을 기준으로 split을 이용하여 판별할 값들을 담는 배열 변수를 만들자.

let split = converted.split("0").filter(x => x.length > 0);
// [ '211', '2', '1', '1', '11' ]

split 배열의 요소들을 하나씩 돌며 소수인지 판별한다. 소수라면 +1을 해준다. 아래와 같이 reduce를 사용해 간단하게 표현하였다.

return split.reduce((a,c) => a += isPrime(c) ,0);

이 후 이 값을 반환하면 끝이다.