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

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

프로그래머스

 

 

🤔 해결방법

1. n을 k진수로 변환한다.

2. 소수의 각 자리에 0이 포함되지 않으므로 0을 기준으로 자른다.

3. 각 숫자가 소수이면 primeCount +1을 한다.

 

 

🔑 풀이

//소수 판별
  function isPrime(num) {
    if (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 primeCount = 0;
    let numbers = n.toString(k).split("0"); // n을 k진수로 변환 후 0을 기준으로 자름

    numbers.forEach((number) => {
      if (number !== "") {
        const num = +number; // 문자열을 숫자로 변환
        if (isPrime(num)) primeCount++;
      }
    });

    return primeCount;
  }

 

 

😭 삽질

처음에 다음과 같은 코드를 짰다.

//소수 판별
  function isPrime(num) {
    if (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 remainder = []; //나머지
    let prime = [];
    let q = 0;
    let r = 0;

    //n이 1이 될 때까지 실행
    while (n !== 1) {
      q = Math.floor(n / k); //n을 k로 나눈 몫
      r = n % k; //n을 k로 나눈 나머지
      remainder.push(r);
      n = q;
    }
    remainder.push(n); //이 때 n는 1

    remainder = remainder.reverse().join("").split("0"); //순서 뒤집고 문자열로 합쳐 연결 후 0을 기준으로 자름

    //비어있지 않은 요소만 numbers에 추가
    let numbers = [];
    for (let i = 0; i < remainder.length; i++) {
      if (remainder[i] !== "") {
        numbers.push(+remainder[i]); //숫자로 변환하여 추가
      }
    }

    //소수면 prime에 추가
    for (let i = 0; i < numbers.length; i++) {
      if (isPrime(numbers[i])) prime.push(numbers[i]);
    }

    return prime.length;
  }

 

그런데 프로그래머스에서 테스트케이스 2번 (110011, 10) 은 통과하였지만 1번 케이스 (437674, 3)는 통과하지 못했다.

'Fatal JavaScript invalid size error 169220804' 에러가 떴는데 보통 js 메모리 크기 제한을 초과했을 때 발생하는 오류라고 한다.

vscode에서는 'Process exited with code 2147483651' 에러가 떴는데 일반적으로 정수 오버플로우가 원인이며 어떤 연산에서 매우 큰 값을 다룰 때 발생하는 오류라고 한다.
큰 숫자를 다루기엔 코드가 비효율적임을 공통적으로 말해주는 것 같았다.😂

 

좀 더 간결한 코드를 위해 다음과 같이 q의 존재를 없애고 마지막 for문 두 개를 합쳤다.

하지만 오류는 여전했다.😂

//소수 판별
  function isPrime(num) {
    if (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 remainder = []; // 나머지
    let primeCount = 0;

    while (n !== 1) {
      let r = n % k; // 나머지 계산
      remainder.push(r);
      n = Math.floor(n / k); // 몫 계산
    }
    remainder.push(n); // n은 1

    let numbers = remainder.reverse().join("").split("0"); // 순서 뒤집고 문자열로 합쳐 0을 기준으로 자름

    numbers.forEach((number) => {
      if (number !== "") {
        const num = +number; // 문자열을 숫자로 변환
        if (isPrime(num)) primeCount++;
      }
    });

    return primeCount;
  }

 

k진수로 변환하기 위해 나머지와 몫을 계산하는 while문도 더 간단하게 바꿀 수 없을까 생각하다 검색을 통해 toString이 진수 변환 기능이 있다는 점을 알게 됐다.😮

여태 문자열 변환용으로만 사용했던 toString이 진수 변환도 할 줄 아는 메소드였다.👍

toString을 사용하니 while문은 아예 필요치 않아 코드가 훨씬 간결해졌고 프로그래머스도 통과시켜줬다.😀

https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Object/toString

Object.prototype.toString() - JavaScript | MDN

 

추가로 소수인지 판별하는 부분은 해당 숫자의 제곱근까지만 나눠서 체크해보면 된다는 것도 알고 있자.

https://velog.io/@rmaomina/%EC%86%8C%EC%88%98%EB%A5%BC-%EC%B0%BE%EC%9D%84-%EB%95%8C-%EC%99%9C-sqrt%EB%A5%BC-%EC%82%AC%EC%9A%A9%ED%95%A0%EA%B9%8C

소수를 찾을 때, 왜? sqrt()를 사용할까?