[프로그래머스 Level 2] k진수에서 소수 개수 구하기 - JavaScript

🔗 문제 링크

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

코딩테스트 연습 - k진수에서 소수 개수 구하기

✏️ 풀이

function solution(n, k) {
    const numbers = n.toString(k).split('0').map(Number);
    return numbers.reduce((acc, num) => {
        if (num <= 1) {
            return acc;
        }
        for (let i = 2; i <= Math.sqrt(num); i++) {
            if (num % i === 0) {
                return acc;
            }
        }
        return acc + 1;
    }, 0);
}

먼저 n을 k진수 문자열로 변환한 후, '0'으로 split하여 소수 여부를 판별할 숫자들을 얻는다.numbers를 순회하면서 2부터 각 숫자의 제곱근까지로 해당 숫자를 나눠보면서 단 한 번이라도 나누어 떨어지면 소수가 아니고, 한 번도 나누어 떨어지지 않으면 소수라고 판단하여 1을 누적한다. numbers 순회가 끝나면 소수가 아닐 때마다 누적된 1의 합으로 소수의 개수를 구할 수 있다.

 

처음에는 에라토스테네스의 체 방식으로 풀려고 했었다. numbers의 최댓값만큼의 길이를 가진 true로 채워진 배열을 만들고, 반복문을 돌면서 나누어 떨어지는 수를 false로 갱신하도록 하였다. 그러나, 생각보다 numbers에 담기게 되는 수의 크기가 엄청 커지기 때문에 배열 길이 제한을 넘기게 되어 런타임 에러가 발생하였다. 

 

다시 생각해보니 연속된 구간에서의 소수의 개수를 구하는 문제도 아니고, 이 문제의 특성상 numbers의 길이도 길게 나오지 않는다. (가장 긴 수가 1,000,000을 2진법으로 바꾼 11110100001001000000이지만 이조차도 numbers의 길이는 4다) 따라서 numbers의 각 수를 순회할 때마다 소수 판별을 하는 것이 더 효율적이다.