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

처리조건

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

풀이

입력으로 들어오는 n을 k진수로 바꾸기위해 toString(진수)를 사용하여 a에 k진수로 변환된 값을 담았다.

문자열b를 빈문자열로 할당하였고 0이나오기전까지 b에다가 쌓다가 0이나오면 지금까지 쌓은 문자를 isPrime함수인자로 넣어 소수를 계산하게 된다. 1은 소수가 아니니까 애초에 검사할 필요가 없으므로 쌓여가던 b가 오로지 1이거나 빈 문자일때는 무시하고 b를 빈 문자로 비우게 된다. 계속 잘 쌓다가 0이 더이상 나오지않고 for문이 끝날 수 있으니 for문의 끝에서 다시한번 0이 나왔을때 하는 검사를 하게된다. 조건문은 같다. 이외에는 정상적으로 계속 b에다가 쌓게된다.

 

isPrime함수를 처음에는 아래와 같이 작성했다.

 

function isPrime(num) {
  if(num === 2)
  return true;

  for(let i = 2; i<=num/2; i++){
    if(num % i === 0){
      return false;
    }
  }
  return true;
}

소수검사할 num을 받게 되는데 2는 소수이므로 바로 true를 리턴하고 num을 2로 나눈 수까지만 2부터 검사하면 된다.

num의 약수는 num의 절반을 넘을 수 없기 때문이다. (시간복잡도는 O(N) 이다.) 만약 나누다가 나머지가 0으로 나오게된다면 나눠 떨어진것이니 이건 소수가 아니겠지?

 

이렇게 소수판별식을 사용하니 테스트1에서 시간초과가 되었고 예전에 썼던 제곱근을 이용해서 소수판별을 했다. 지금은 num을 2로 나눈 수까지 for을 돌리지만 num의 제곱근보다 큰 수까지는 돌릴필요가 없고 판별할 범위가 더 줄어든다.

그래서 범위를 i<= Math.floor(Math.sqrt(num))으로 지정했다. floor은 정수자리만때고, sqrt는 제곱근처리한다.

function isPrime(num) {
  
  if(num === 2) {
    return true;
  }
  
  for(let i = 2; i <= Math.floor(Math.sqrt(num)); i++){
    if(num % i === 0){
      // 한 번이라도 나누어 졌으니 소수가 아니므로 return false
      return false; 
    }
  }
  // 나눠진 수가 없다면 해당 수는 소수이므로 return true
  return true; 
}

 

이렇게 소수판별식 까지 if문에서 마치게 되면 true를 뿜고 count++를 하게 될 것이다. 

 

function solution(n, k) {
  let a = (n.toString(k));
  let b = "";
  let count = 0;
    
  for (let i = 0; i < a.length; i++) {
    if (a[i] === "0") {
      if (b !== "1" && b !== "" && isPrime(Number(b))) {
        count++;
      }

      b = "";
      continue;
    } else if (i === a.length - 1) {
      b += a[i];
      if (b !== "1" && b !== "" && isPrime(Number(b))) {
        count++;
      }
      b = "";
    }
    b += a[i];
  }
  return count;
}
function isPrime(num) {
  if (num === 2) {
    return true;
  }

  for (let i = 2; i <= Math.floor(Math.sqrt(num)); i++) {
    if (num % i === 0) {
      // 한 번이라도 나누어 졌으니 소수가 아니므로 return false
      return false;
    }
  }
  // 나눠진 수가 없다면 해당 수는 소수이므로 return true
  return true;
}