[프로그래머스] k진수에서 소수 개수 구하기(LV.2) by javascript - 2022 KAKAO BLIND RECRUITMENT

▷ 문제 : 2022 KAKAO BLIND RECRUITMENT - k진수에서 소수 개수 구하기 LV.2

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

▷ 해결 날짜 : 2022.03.08
▷ 소요 시간 : 50분
▷ 풀이 과정 :

양의 정수 n을 k진수로 바꿨을 때, 변환된 수 안에 조건에 맞는 소수를 찾는 문제이다.

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

이번 문제는 소수 찾는 방법만 알고 있다면 손쉽게 풀 수 있는 문제였다.

 

우선 "0"을 기준으로 소수를 체크하기 때문에 "0"으로 나눈 뒤 나머지 값들 중에서 소수를 찾으면 되는 것이다.

하나 에라토스테네스의 체를 이용해 문제를 풀던 나는 에러에 봉착하여 시간이 좀 걸렸다.

에라토스테네스의 체를 제거하고 단순하게 제곱근을 사용하여 소수를 찾아주었다.

 

▷ 구현

function solution(n, k) {
    let primes = n.toString(k).split('0').filter(e => e);
    let isPrimes = primes.filter(e => isPrime(Number(e)));
    return isPrimes.length;
}

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

▷ 복기 :
지금까지 풀어왔던 방식으로 풀었거늘 에러가 발생해 멍 때리느라 시간이 지체되었다.

이걸 기점으로 소수 관련 문제는 뭔가 친숙(?)해진 느낌이 든다.