[JS] k진수에서 소수 개수 구하기

2022 카카오 블라인드 채용에서 나온 문제였네요.

런타임에러를 조심해야하는 문제입니다.

같이 한번 살펴봐요!

---

문제 요약

 437674을 3진수로 바꾸면 211020101011입니다. 여기서 찾을 수 있는 조건에 맞는 소수는 왼쪽부터 순서대로 211, 2, 11이 있으며, 총 3개입니다. (211, 2, 11을 k진법으로 보았을 때가 아닌, 10진법으로 보았을 때 소수여야 한다는 점에 주의합니다.) 211은 P0 형태에서 찾을 수 있으며, 2는 0P0에서, 11은 0P에서 찾을 수 있습니다.

정수 n과 k가 매개변수로 주어집니다. n을 k진수로 바꿨을 때, 변환된 수 안에서 찾을 수 있는 위 조건에 맞는 소수의 개수를 return 하도록 solution 함수를 완성해 주세요.

 

제한사항

• 1 ≤ n ≤ 1,000,000
• 3 ≤ k ≤ 10

테스트케이스

n	k	result
437674	3	3
110011	10	2

 

접근 방법

진수 전환은 javascript를 사용하면 toString(n)으로 간단하게 할 수 있습니다.그리고 소수인지 판별하는 방법에서 주의하셔야 할게 평소에 에레토스테네스의 체 사용하실 때 판별할 숫자 n을 기준으로 배열을 만들어서 하면 런타임에러가 납니다.아마 낮은 진수에서 자릿수가 엄청 커서 (만약에 511을 2진수로 바꾸면 111,111,111이니 공간을 약 천 만개 만들어야 하네요.)스택을 넘어가지 않을까 싶습니다.

 

그래서 관성적으로 배열을 만들지 말고 각각 값에 대해 소수인지 판별하는 작업을 수행하시면 런타임에러에는 안걸릴 것 같습니다.같이 한번 확인하시죠!

 

정답 코드

function solution(n, k) {
    const nk = n.toString(k).split("0");
    let result = 0;
    
    nk.forEach(v => {
        if(isPrime(v)) result++;
    });
    return result;
    
    function isPrime(num) {
        for(let i = 2, s = Math.sqrt(num); i <= s; i++)
            if(num % i === 0) return false; 
        return num > 1;
    }
}

 

팁 1. n진수로 전환하고 0기준으로 쪼개기

const nk = n.toString(k).split("0");

 

문제 설명을 유의깊게 읽어보시면 알 수 있듯이 이 문제는 0기준으로 간단히 split 해주면 원하는 소수를 얻을 수 있습니다.

또, toString(n)을 통해 간단히 n진수로 변환이 가능합니다.

 

팁 2. 소수의 판별

function isPrime(num) {
    for(let i = 2, s = Math.sqrt(num); i <= s; i++)
        if(num % i === 0) return false; 
    return num > 1;
}

 

에라토스테네스 최적화에 따르면 n이 소수인지 판단하기 위해서는 n의 제곱근이하 에서 약수가 있는지 판단하면 됩니다.

쭉 순회하다가 나눠진다면 false를 return하고 1일 경우를 생각해서 return해주면 되겠습니다.

 

이문제는 생각보다 쉬웠네요.

그럼 이만!