[프로그래머스 / javascript / js] k진수에서 소수 개수 구하기

문제 설명

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

• 0P0처럼 소수 양쪽에 0이 있는 경우
• P0처럼 소수 오른쪽에만 0이 있고 왼쪽에는 아무것도 없는 경우
• 0P처럼 소수 왼쪽에만 0이 있고 오른쪽에는 아무것도 없는 경우
• P처럼 소수 양쪽에 아무것도 없는 경우
• 단, P는 각 자릿수에 0을 포함하지 않는 소수입니다.
  • 예를 들어, 101은 P가 될 수 없습니다.

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

예시) 437674을 3진수로 바꾸면 211020101011 입니다. 여기서 찾을 수 있는 조건에 맞는 소수는 왼쪽부터 순서대로 211, 2, 11이 있고 총 3개입니다.

풀이

위의 조건에서 각 숫자 양옆에 0이 없는 숫자가 소수인지를 판별해서 그 갯수를 얻어야하는 문제라고 이해를 했다.

그래서 수도코드를 작성해보자면

1. k진수로 변환한다.
2. 변환된 수에서 0을 기준으로 나눠준다.
3. 나눠진 숫자를 가지고 소수인지 판별한다.
4. 소수 갯수를 카운트해서 그 값을 리턴한다.

아래는 내가 작성한 코드이다.

function solution(n, k) {
    // k진수로 변환해서 0으로 구분
    let result = []
    while(n > 0){
        result.unshift(n % k);
        n = Math.floor(n / k);
    }
    const convertedNums = result.join("").split('0');
    
    // 구분된 숫자를 소수인지 확인해서 맞으면 count에 +1
    let count = 0;
    for(let i = 0; i < convertedNums.length; i++){
        const num = Number(convertedNums[i]);
        if(convertedNums[i] === '') continue;
        if(isPrime(num)) count++;
    }
    return count;
}

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

풀고나서 다른 사람 코드를 보니 n.toString(k)를 해주면 k진수로 변환된 수를 문자열로 만들어 줄 수 있는 것 같다.

그래서 mdn을 찾아보았더니 Number 객체에서 toString() 메소드는 특정 진수로 객체를 표현한 문자열을 환원합니다.

numObj.toString([radix])

위처럼 매개변수(radix(Optional)수의 값을 나타내기 위해 사용되기 위한 기준을 정하는 2와 36사이의 정수(진수를 나타내는 기수의 값))를 넣어주면 k진수를 만들 수 있다.

이것을 이용해서 코드를 좀 더 간결하게 해보았다.

function solution(n, k) {
    let nums = n.toString(k).split("0");
    return nums.filter(el => el !== "" && isPrime(Number(el))).length;
}

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