최종 풀이
function isPrime(num) {
if (isNaN(num) || num < 2) return false; // 숫자가 아니거나 2보다 작으면 소수아님
if (num === 2 || num === 3) return true; // 소수 2,3 예외처리 (루트 씌웠을 때 고려)
for (let i = 2; i <= Math.sqrt(num); i++) {
if (num % i === 0) return false;
}
return true;
}
function solution(n, k) {
let answer = 0;
// n을 k진법으로 변환 -> 0을 기준으로 split -> 숫자로 변환
const list = n.toString(k).split('0').map(i => parseInt(i));
// 소수 판별
list.forEach((num) => {
if (isPrime(num)) answer++;
})
return answer;
}💡 핵심 아이디어
- n을 k진법으로 변환한다
- 0을 기준으로 split 후 숫자로 변환한다 (숫자가 아닌 예외 케이스
""고려)- 각 요소가 소수인지 체크한다.
😵💫 부딪혔던 문제
1. 문제 잘못 이해
문제 조건에 맞는 소수를 k진법으로 변환 후, k진법으로 보았을 때가 아닌, 10진법으로 보았을 때 소수여야 한다 는 뜻을 잘못 이해해서 k진법으로 변환 후 → 다시 10진법으로 변환했을 때 소수여야한다고 이해했다.
그게 아니라
k진법으로 변환했을 때 그 수 자체를 10진법의 수로 봐도 된다..였다.
const list = n.toString(k).split('0').map(x => parseInt(x, k);
해결법
중간에 k진법으로 읽어서 → 10진법으로 변환하는 map(x => parseInt(x, k) 에서 parseInt의 두 번째 인자 k를 삭제했다
const list = n.toString(k).split('0').map(i => parseInt(i));받아서 바로 number 형태로 변환하는 식!
2. 소수 구하기
// 소수인지 확인
list.forEach((num) => {
let cnt = 0;
// 1과 자기자신으로만 나누어지면 소수
for (let i = 1; i <= num; i++) if (num % i === 0) cnt++;
if (cnt === 2) answer++;
})처음에는 그저 소수는 1과 자기 자신으로만 나누어지면 된다! 라는 단순한 생각으로
1부터 num까지 순회하며 모든 요소로 나누어서 cnt === 2이면 소수이다 라고 코드를 짰다.
물론 틀린 코드는 아니다.
하지만 num이 한 없이 커질 때 (ex. num = 100,000…)는 이 모든 수를 처음부터 끝가지 순회해야한다는 문제가 생긴다.
당연하게도 시간초과 오류가 났다.
해결법 : Math.sqrt(num)까지만 순회하기!
for (let i = 2; i <= Math.sqrt(num); i++) {
if (num % i === 0) return false;
}2부터 Math.sqrt(num) 까지만 순회해도 num의 모든 약수쌍을 순회할 수 있다.
만약, num을 어떤 수로 나눠서 나누어 떨어진다면,
그 나눈 수(a)와 몫(b)이 두개가 존재한다.
예를 들어, 36의 약수 쌍은
(1, 36) (2, 18) (3, 12) (4, 9) (6, 6)
이 약수 쌍에서 볼수 있듯이 나누어 떨어지는 두 수 중에
하나의 수가 커지면 하나의 수가 작아진다.
그러다 두 수가 점점가까워지는 지점이 바로 제곱근이기 때문에,
만약 2부터 Math.sqrt(num) 까지 어떤 수로도 나누어떨어지지 않으면,
그보다 큰 어떤 수로도 나누어 떨어질 수 없다!
(이미 그보다 작은 약수 쌍에 의해 검증되었기 때문에)
배운 점 및 향후 개선점
parseInt가 두 번째 인자를 받을 수 있고, 이것이 어떤 기능을 하는 지에 대해 알수 있었다.- 소수의 개수를 효율적으로 구하는 코드를 알수 있었다.
→ 어떻게하면 더 효율적으로 코드를 작성할 수 있을지 고민하기!
