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

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

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

2022 KAKAO BLIND RECRUITMENT

LEVEL 2

문제설명

양의 정수 n을 k진수로 바꾸었을 때 다음 조건을 만족하는 소수(P)의 개수를 구하는 solution 함수를 작성하시오.

• 0P0 : 소수 양쪽에 0이 있는 경우
• P0 : 소수 오른쪽에만 0이 있고 왼쪽에는 아무것도 없는 경우
• 0P : 소수 왼쪽에만 0이 있고 오른쪽에는 아무것도 없는 경우
• P : 소수 양쪽에 아무것도 없는 경우
• 단, P는 각 자릿수에 0을 포함하지 않는 소수 (P는 십진법으로 보아야 함)

INPUT

n

• 양의 정수
• 1 ≤ n ≤ 1,000,000

k

• 양의 정수
• 3 ≤ k ≤ 10

OUTPUT

• n을 k진수로 바꾸었을 때, 주어진 조건을 만족하는 소수의 개수 (0이상의 정수)

나의 풀이

1. toString을 사용해 n을 k진수로 변환한 문자열 nStr을 만든다.
2. nStr을 0으로 split한 후 각 요소를 10진법 숫자로 바꾼 배열 nArr을 만든다.
   • 빈 문자열 ('')은 filter를 사용해 배열에서 제거한다.
3. nArr의 요소들 중 소수인 요소들의 개수를 count에 담은 뒤 return한다.
   • 인자로 주어진 정수가 소수인지 아닌지 판별하는 함수 isPrime을 작성한다.

function solution(n, k) {
    // 1. nStr : toString을 사용해 n을 k진수로 변환한 문자열
    const nStr = n.toString(k);
  	// 2. nArr : nStr을 0으로 split한 후 각 요소를 10진법 숫자로 바꾼 배열
    const nArr = nStr.split('0').filter(el => el.length !== 0).map(el => parseInt(el, 10));
  	// 3. count : nArr의 요소들 중 소수인 요소들의 개수
    const count = nArr.filter(el => isPrime(el)).length;
    return count;
}

// isPrime : 소수인지 아닌지 판별하는 함수 (n은 정수)
function isPrime(n) {
    if (n <= 1) return false; // 0, 1은 소수가 아님
    if (n === 2 || n === 3) return true; // 2, 3는 소수
    if (n % 2 === 0) return false; // 2를 제외한 짝수는 소수가 아님
    for (let i = 3, m = Math.sqrt(n); i <= m; i += 2) {
        // 3 ~ Math.sqrt(n) 까지의 홀수들로 n을 나누어 나누어 떨어지는지 확인
        if (n % i === 0) return false;
    }
    // for문이 끝날때까지 return false되지 않았다면 소수
    return true;
}