[Javascript/자바스크립트] (프로그래머스) k진수에서 소수 개수 구하기

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

정답 코드

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;
}

function solution(n, k) {
  let answer = 0;
  // 0으로 split
  const numArr = n.toString(k).split("0");
  // 에라토스테네스의 체 실행 & 소수 판별해줄 함수 리턴
  for (const num of numArr) {
    isPrime(parseInt(num)) && answer++;
  }
  return answer;
}

 

문제 풀이 과정

1. 에라토스테네스의 체 이용

문제 풀이 과정

소수를 판별하기 위한 알고리즘인 "에라토스테네스의 체"를 이용하여 문제를 풀이하려 했다. 

- 소수인지 판별하기 위한 함수 `prime`
1. 에라토스테네스의 체로 어떤 수가 소수인지 미리 구해놓는다.
2. 인자로 받은 수가 소수인지 판별하는 함수 `isPrime`을 리턴한다.

- `solution` 동작 과정
1. n을 k진수로 변환
2. '0'으로 splilt
3. split의 결과로 생성된 배열에 대해 isPrime을 실행하여 배열의 각 원소가 소수인지 판별
4. 소수의 개수를 리턴

 

아래와 같은 코드로 구현했었다.

// 에라토스테네스의 체로 소수 구하기 (0이 들어간 소수는 제외)
// prime이 리턴하는 isPrime는 인자로 받은 수 n이 소수인지 아닌지 판별하는 함수

// 문제 풀이
// 1. k진수로 변환
// 2. 0으로 split
// 3. split된 후에 남은 각 숫자가 소수인지 확인

function prime(kNumString) {
  // 에라토스테네스의 체
  const kNum = parseInt(kNumString);
  const arr = new Array(kNum + 1).fill(true);
  arr[0] = false;
  arr[1] = false;
  for (let i = 2; i <= kNum; i++) {
    if (arr[i]) {
      for (let j = i * 2; j <= kNum; j += i) {
        arr[j] = false;
      }
    }
  }

  function isPrime(numString) {
    const num = parseInt(numString);
    return arr[num];
  }
  return isPrime;
}

// n을 k진수 문자열로 변환
function convertKNum(n, k) {
  return n.toString(k);
}

function solution(n, k) {
  let answer = 0;
  // k진수 변환
  const kNum = convertKNum(n, k);
  // 0으로 split
  const numArr = kNum.split("0");
  // 0으로 split한 배열에서 최대값 구하기
  let maxNum = 0;
  numArr.map((num) => {
    if (maxNum < num.toString()) {
      maxNum = num.toString();
    }
  });
  // 에라토스테네스의 체 실행 & 소수 판별해줄 함수 리턴
  const isPrime = prime(maxNum);
  for (const num of numArr) {
    isPrime(num) && answer++;
  }
  return answer;
}

// console.log(solution(437674, 3));
// console.log(solution(110011, 10));

이 풀이의 문제점

테스트케이스를 돌려보니 런타임 에러가 발생하는 케이스들이 있었다.

문제를 찾아보니 number의 범위 때문에 에러가 발생하는 것 같았다.

 

문제의 조건에서 n의 범위는 1 ≤ n ≤ 1,000,000 이다. 이 수들 중 2진법으로 변환하면 "10111111111111111111"이 나오는 경우가 있다. 이런 경우에는 111,111,111,111,111,111(1이 18개, 10진수로 보면 약 11경)이 소수인지 판별해야 하는데, 내가 작성한 코드에서 보면 소수인지 판별하기 위해서는 이 크기의 배열을 만들어야 한다.

 

근데 11경의 배열...? 당연히 가능할리가 없다. 자바스크립트의 배열의 최대 크기는 2^32이다. 그렇기 때문에 에라토스테네스의 체는 이용할 수 없을 것이라고 생각하여 이 풀이는 폐기했다. 

 

2. 소수 판별 시 2부터 나눠지는 수가 있는지 확인

가장 간단하게 소수를 판별할 수 있는 방법이다.

소수(素數, [소쑤]): 수학에서 1과 그수 자신 이외의 자연수로는 나눌 수 없는, 1보다 큰 자연수.

 

소수의 정의가 이렇기 때문에 2부터 하나씩 숫자를 키워가며 나눠지는 경우가 있는지 확인하면 소수인지 판별할 수 있다. 

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;
}

이렇게 하면 배열을 만들 필요가 없으므로 배열의 범위 걱정은 해도 되지 않게 된다. 

그리고 이 경우에도 for문을 너무 많이 돌지 않을까 걱정이 될 수도 있는데, 제곱근까지만 for문을 돌기 때문에 이 문제의 숫자 범위 내에서는 괜찮다.

아까 예시로 들었던 111,111,111,111,111,111의 경우에도 제곱근을 구해보면 333333333이고, 이렇게 극단적으로 길게 나오는 경우에는 k진법으로 변환한 수가 "10111111111111111111"와 같이 이 수 이외에는 큰 수가 대부분 안 나온다. 그렇기에 충분히 해볼만 하다.

 

코드 풀이

코드는 가장 위에 있다.

처음 풀이에서 다 풀어서 풀이했던 것도 결국은 중간 과정의 값들이 필요가 없으므로, n을 k진수로 변환하고 '0'으로 split하는 과정은 method chaining을 이용하여 한 줄로 줄였다.

그리고 split한 뒤 배열의 각 원소를 위에서 말한 `isPrime` 함수로 판별하여 소수가 몇 개인지 구했다.

 

느낀 점

소수 판별을 위해 에라토스테네스의 체를 생각해낸 점은 좋았으나, n을 k 진법으로 변환했을 때 최악의 경우를 구하고 이것이 가능한 배열의 범위 내에 있는지 확인하는 과정을 미리 가졌다면 좋았을 것 같다.

 

문제의 조건을 잘 보자!