[TIL #14] k진수에서 소수 개수 구하기

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

프로그래머스

2022년 카카오 블라인드 채용 문제다.

 

문제를 보고 나서 든 생각은, "아니 이게 뭔 소리야?".

하여간 코딩테스트 문제는 까보면 요구사항은 별거 없는데 설명을 장황하게 하는 것 같다.

 

결국 숫자 ``n``을 ``k``진법 ``kn``으로 바꾸고, 그 수를 10진법 수로 가정한다.

``kn``에서 찾을 수 있는 소수의 개수를 리턴하는 문제인 것이다.

 

"오케이... 일단 수를 처음부터 스캔하면서 가야 하니 슬라이딩 윈도우면 되겠는데?"

라고 생각하며 다음의 코드를 작성했다.

 

// k진법으로 변환
// 윈도우를 옮겨가며 소수 확인, 0은 포함하지 않음
// 판별 후 윈도우 시작지점 이동

function isPrime(n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 === 0 || n % 3 === 0) return false;

    const sqrt = Math.sqrt(n);
    for (let i = 5; i <= sqrt; i += 6) {
        if (n % i === 0 || n % (i + 2) === 0) return false;
    }

    return true;
}

function solution(n, k) {
    const converted = n.toString(k);
    const len = converted.length;
    let cnt = 0;
    let left = 0;
    let right = 0;
    
    while(right <= converted.length) {
        // 윈도우의 끝이거나 현재 right가 0일 경우
        if(right === len || converted[right] === '0') {
            
            // 필요한 부분만 slice
            const slicedNum = converted.slice(left, right);
            // ''인 경우가 생길 수도 있음
            if(isPrime(slicedNum) && slicedNum !== '') {
                cnt++;
            }
            // 윈도우 이동
            right++;
            left = right;
        }
        else {
            right++;
        }
    }
    
    return cnt;
}

소수 판별 함수는 전에 만들어 둔 것을 가져왔다.

0을 기준으로 하여 소수를 판별해야 한다.

따라서 윈도우의 끝에 0이 있는지 계속 확인한 것이다.

 

그런데 다 풀고 나니 뭔가 아쉬웠다.

왠지 더 좋은 방법이 있을 거 같긴 한데 떠오르질 않으니...

그러다가 '0이 기준이라는 점'에 꽂혔다.

그렇다면 0을 다 없애고 남은 숫자들에 대해서 소수 판별을 하면 되는 것이 아닌가?

그렇게 다음의 코드가 나왔다.

 

function solution(n, k) {
    const converted = n.toString(k);
    const splited = converted.split('0');
    let cnt = 0;
    
    for (let num of splited) {
        if (num === '') continue;
        if (isPrime(num)) cnt++;
    }
    
    return cnt;
}

어떻게 보면 어이가 없을 정도.

``k``진법으로 변환하고,

0을 기준으로 분리하고,

그게 소수인지 확인하면서 카운팅 하면 끝.

 

이런 게 바로바로 떠올라야 하는데 내공이 너무 부족하단 말이지...