[프로그래머스] K진수에서 소수 개수 구하기 (JavaScript)

잭슨·2024년 8월 27일

자바스크립트 프로그래머스

알고리즘 문제 풀이

목록 보기

126/130

문제

k진수에서 소수 개수 구하기

요구사항 분석

문제 의도

빌트인 메서드 등을 활용하여 진수를 변환할 수 있는가
소수를 판별하는 기능을 구현할 수 있는가

분석

문제 설명에서 P 의 조건이 여러개 주어서 헷갈릴 수 있지만 정리해보자면 P는 "0을 제외하고 연결되어있는 자연수" 라고 생각하면 된다.

예를 들어 k진수로 변환한 수가 "010042401"이라면 1, 424, 1이 소수인지 판별하면 된다.

풀이

function solution(n, k) {
    let answer = 0;
    const kFormationNum = n.toString(k);
    
    for(let i=0; i<kFormationNum.length;){
        while(kFormationNum[i] === '0') i++;
        let j = i;
        while(kFormationNum[j] !== '0' && j < kFormationNum.length) j++;
        const p = kFormationNum.slice(i,j);
        if(isPrimeNumber(+p)) answer++;
        i = j;
    }
    
    return answer;
}

function isPrimeNumber(num){
        if(num === 0 || num === 1) return false;
        for(let i=2; i<=Math.sqrt(num); i++){
            if(num % i === 0) return false;
        }
        return true;
}

풀이 설명

"0을 제외하고 연결되어 있는 자연수"를 선택하기 위해 solution 함수에서 for 문을 돌아준다.

i는 0이 아닌 수의 시작지점에서 멈추고, j는 i에서부터 0이 등장할 때까지 1씩 증가한다. 그러면 j가 멈췄을 때, kFormationNum[i] ~ kFormationNum[j-1]은 "0을 제외하고 연결되어 있는 자연수" 즉, p가 된다.

또한 kFormationNum의 마지막 숫자가 0으로 끝나지 않는 경우 j가 무한히 증가할 수 있기 때문에 j < kFormationNum.length라는 조건도 걸어둔다.

p가 결정되었으면 p가 소수인지 판별하기 위해 isPrimeNumber 함수에 전달한다. isPrimeNumber 함수는 "하나의 수를 그 수의 제곱근 까지 1씩 증가시키며 나누어서 나누어 떨어지면 소수가 아니고, 나누어 떨어지는 수가 없으면 소수다." 라는 논리에 의거한 기본적인 소수 판별 알고리즘이다.

1은 소수가 아니기 때문에 num이 1일 경우에는 false를 리턴해준다. 여기서 조금 특별한 케이스는 num에 0이 들어오는 케이스다.

solution 함수에서 i와 j가 동일한 경우, p는 공백('')되는데 이것이 Number 타입으로 변환되어 0이 isPrimeNumber 함수에 전달된다. 그러면 반복문을 거치지 않고 true를 반환하기 때문에 잘못된 결과가 나온다.

이 예외 처리를 해주지 않으면 "테스트케이스 12번" 에서 틀리게 되므로 이러한 조건을 걸어주었다.

시행착오

TestCase 12

위의 풀이 설명에서도 말했듯이, 소수를 판별하는 함수에 0이 전달된 경우를 테스트하는 케이스로 추정된다.

그래서 num에 0이 전달되는 경우가 어떤 경우가 있을까 생각해봤다.

kFormationNum이 0으로 끝날 경우 i는 kFormationNum.length까지 증가하고 j또한 kFormationNum.length가 된다. 즉, i와 j가 같아지고, slice메서드는 start 보다 end-1이 더 작을 경우 공백('')을 반환한다. 따라서 p는 공백('')이 되고, 공백은 타입 변환에 의해 0이 된다.

이러한 경우 때문에 isPrimeNumber함수에 0이 전달된 경우 예외처리를 해주어야 한다.

TestCase 1,11

에라토스테네스의 체를 이용해서 풀어보려고 했을 때 TestCase 1번과 11번에서 런타임 에러가 발생했다.

코드는 다음과 같다.

function solution(n, k) {
    let answer = 0;
    const kFormationNum = n.toString(k);

    for (let i = 0; i < kFormationNum.length - 1; ) {
        while (kFormationNum[i] === '0') i++;
        let j = i;
        while (kFormationNum[j] !== '0' && j < kFormationNum.length) j++;
        const p = kFormationNum.slice(i, j);
        if (isPrimeNumber(+p)) answer++;
        i = j;
    }

    function isPrimeNumber(num) {
        if (num === 0 || num === 1) return false;
        const primeNumber = Array(num + 1).fill(true);
        for (let i = 2; i <= Math.floor(Math.sqrt(num)); i++) {
            if (primeNumber[i]) {
                // i가 소수인 경우
                let j = 2;
                while (j * i <= num) {
                    primeNumber[j * i] = false;
                    j++;
                }
            }
        }
        return primeNumber[num];
    }
    return answer;
}