문제

양의 정수 n이 주어집니다. 이 숫자를 k진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 알아보려 합니다.

0P0처럼 소수 양쪽에 0이 있는 경우
P0처럼 소수 오른쪽에만 0이 있고 왼쪽에는 아무것도 없는 경우
0P처럼 소수 왼쪽에만 0이 있고 오른쪽에는 아무것도 없는 경우
P처럼 소수 양쪽에 아무것도 없는 경우
단, P는 각 자릿수에 0을 포함하지 않는 소수입니다.
예를 들어, 101은 P가 될 수 없습니다.
예를 들어, 437674을 3진수로 바꾸면 211020101011입니다. 여기서 찾을 수 있는 조건에 맞는 소수는 왼쪽부터 순서대로 211, 2, 11이 있으며, 총 3개입니다. (211, 2, 11을 k진법으로 보았을 때가 아닌, 10진법으로 보았을 때 소수여야 한다는 점에 주의합니다.) 211은 P0 형태에서 찾을 수 있으며, 2는 0P0에서, 11은 0P에서 찾을 수 있습니다.

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

입력

n : 437674
k : 3

출력

3

제한 사항

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

내가 했던 풀이 방법

이 문제는 소수 판별 알고리즘을 어떤 것을 쓰느냐에 따라 정답 여부가 갈린다.
1. 변환된 수 중 가장 큰 값을 에라토스테네스의 체 알고리즘 사용 -> 일부 테이스 케이스 런타임 오류 발생 (소수 판별해야 하는 수 중에 매우 큰 수가 있어 메모리 효율이 나쁨)
2. 각각의 수를 기본 소수 판별 알고리즘 (2부터 n-1까지) 사용 -> 시간 초과
3. 각각의 수를 n/2까지 소수 판별 알고리즘 사용 -> 시간 초과
4. 각각의 수를 n의 제곱근까지 소수 판별 알고리즘 사용 -> 성공

1. k가 10일 경우, cal을 n으로 저장해준다. 이때, n을 문자열로 변환해준다. k가 10이 아닐 경우, n을 k진수로 변환해준 값을 n에 저장해준다. (변환 return 값은 문자열이다.)
2. cal을 0을 기준으로 분할해준다. 이때 ""도 포함되므로, filter를 이용해 ""을 제외한 수만 Number형으로 변환해 numbers에 저장해준다.
3. numbers에 있는 모든 수를 소수 판별 알고리즘(제곱근 활용)을 사용해 검사해준 뒤, 해당 값이 true이면 answer를 1 증가시켜준다.
4. answer를 반환한다.

코드

function solution(n, k) {
    let answer = 0;
    let cal = "";
    if(k!==10) {
       cal = conversion(n, k);
    } else {
        cal = n+"";
    }
    
   let numbers = cal.split("0").filter(str=>str!=="").map(Number);
    for(let i=0; i<numbers.length; i++) {
        if(isPrime(numbers[i])) {
            answer++;
        }
    }
    return answer;
}

function conversion(n, k) {
    let result = "";
    while(true) {
        if(n===0) break;
        result = (n%k) + result;
        n = Math.floor(n/k);
    }
    return result;
}

function isPrime(n) {
    if(n===1) return false;
    for(let i=2; i*i<=n; i++) {
        if(n%i===0) {
            return false;
        }
    }
    return true;
}

회고

의외로 문제를 처음 읽고 진수 변환 후 수를 찾아내는 것이 어렵겠다고 생각했는데, 실제로 구현해보니 문제에서 오히려 겁을 준 것 같다. 저렇게 생각할 필요가 전혀 없었던 문제. 그냥 0을 기준으로 수가 분할된다고 생각하니 구현할 방법이 바로 떠올랐던 것 같다. 의외로 속을 썩인 건 소수 판별 부분인데 어쩜 소수 관련 문제는 풀 때마다 한 번씩은 틀려주는지 모르겠다. 어떤 때는 이 알고리즘을 쓰면 시간초과가 나고, 또 다른 문제는 이 알고리즘을 써야하고... 우짜란 말이냐...ㅠ 이번에도 당연히 소수 판별에 에라토스테네스의 체를 안 쓰면 시간초과 나겠지?하고 구현해놓은 코드를 수정하니 이렇게 구현하지말라네.... 어휴... 소수는 참 쉬우면서도 어려운 것 같다...