문제 설명
양의 정수 n이 주어집니다. 이 숫자를 k진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 알아보려 합니다.
- 0P0처럼 소수 양쪽에 0이 있는 경우
- P0처럼 소수 오른쪽에만 0이 있고 왼쪽에는 아무것도 없는 경우
- 0P처럼 소수 왼쪽에만 0이 있고 오른쪽에는 아무것도 없는 경우
- P처럼 소수 양쪽에 아무것도 없는 경우
- 단, P는 각 자릿수에 0을 포함하지 않는 소수입니다.
- 예를 들어, 101은 P가 될 수 없습니다.
예를 들어, 437674을 3진수로 바꾸면 211020101011입니다. 여기서 찾을 수 있는 조건에 맞는 소수는 왼쪽부터 순서대로 211, 2, 11이 있으며, 총 3개입니다. (211, 2, 11을 k진법으로 보았을 때가 아닌, 10진법으로 보았을 때 소수여야 한다는 점에 주의합니다.) 211은 P0 형태에서 찾을 수 있으며, 2는 0P0에서, 11은 0P에서 찾을 수 있습니다.
정수 n과 k가 매개변수로 주어집니다. n을 k진수로 바꿨을 때, 변환된 수 안에서 찾을 수 있는 위 조건에 맞는 소수의 개수를 return 하도록 solution 함수를 완성해 주세요.
제한사항
- 1 ≤ n ≤ 1,000,000
- 3 ≤ k ≤ 10
입출력 예
| n | k | result |
| 110011 | 10 | 2 |
| 437674 | 3 | 3 |
입출력 예 #1
문제 예시와 같습니다.
입출력 예 #2
110011을 10진수로 바꾸면 110011입니다. 여기서 찾을 수 있는 조건에 맞는 소수는 11, 11 2개입니다. 이와 같이, 중복되는 소수를 발견하더라도 모두 따로 세어야 합니다.
나의 풀이
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 answer = 0,prime,stack=[],arr=[]
prime=(n.toString(k)+"").split("0")
for(let i=0;i<prime.length;i++){
if(isPrime(prime[i]))
answer++
}
return answer
}풀이 전략
1. prime에 주어진 n을 진수 변환 후 0으로 잘라 실제 소수인지 판별할 수를 넣는다
2. prime 배열을 순회하며 소수인지 판별
2-1. 소수인지 판별하는 isPrime()함수는 2부터 제곱근 수까지 나누는 수가 존재하면 바로 false return , 존재하지 않는 경우 true return
?? 왜 제곱근 수냐 ??
제곱근(sqrt) 범위 나누기법이란?
소수 여부를 검사할 수에 대해서 그 값의 제곱근을 기준으로 그 곱은 대칭적으로 곱이 일어나므로 제곱근 이하의 작은 값까지만 검사를 하면 나머지는 검사를 할 필요가 없다는 방법으로 검사할 데이터를 제곱근 개 이하로 줄 일 수 있는 방법이다.
예). 18로 예를들면, 18의 약수는 1, 2, 3, 6, 9, 18이며,
18은 1 * 18, 2 * 9, 3 * 6 < √18 > 6 * 3, 9 * 2, 18 * 1 이다.
√18 * √18도 18인데, 이 √18을 좌우로 곱하기가 대칭이므로 sqrt()값보다 같거나 작은 숫자로 나누어지면 그 이후에 대해서는 대칭이므로 계산을 할 필요가 없다는 원리로 검사하려는 수의 제곱근 값 이하의 수만큼 체크하면 되는 기법이다.
√18의 값은 4.242... 이므로 4까지 나누어 떨어지지 않으면 소수가 아니라는 의미이며 큰 수도 몇번의 계산으로 확인가능하다는 장점이 있다.