프로그래머스 k진수에서 소수 개수 구하기 JavaScript
2022년 12월 31일
제한사항
- 1<= n <= 1,000,000
- 3<= k <= 10
문제풀이
구현 문제,
- k 진수로 변환 kBaseConversion
- 손으로 계산할 때와 유사하게 나누어지지 않을 때까지 나누는 방식
- 나누는 중 나머지를 계속 더해주고 마지막으로 남은 값(<k)도 더한 다음 문자열을 뒤집어 반환
- 소수 체크 primeCheck
- 소수를 확인하는 방법으로는 x-1까지의 모든 값들로 나누어 보기
- x/2까지의 값들로 나누어 보기
- x의 제곱근까지의 값들로 나누어보기
- 각각 시간 복잡도는 O(n), O(n/2), O(√n)
- 가장 빠른 세 번째 방법으로 구현했다.
- 소수 개수 세기 primeCount
- 주어진 n은 문자 타입, n의 index 0 번부터 조회
- '0'이 아니면 임시 문자열에 값을 더하고
- '0'일 경우 이때 임시 문자열의 값이 소수일 경우 cnt++
solution.js
function solution(n, k) {
let answer = 0;
const kBaseNum = kBaseConversion(n, k);
answer = primeCount(kBaseNum);
return answer;
}
function kBaseConversion(n, k) {
let temp = '';
let num = n;
let remain = 0;
while (num >= k) {
remain = num % k;
num = Math.floor(num / k);
temp += String(remain);
}
temp += String(num);
return temp.split("").reverse().join("");
}
function primeCheck(n) {
if (n === 1) return false
if (n === 2) return true;
for (let i = 2; i <= Math.floor(Math.sqrt(n)); i++) {
if (n%i === 0) return false;
}
return true;
}
function primeCount(n){
let temp = '';
let cnt = 0;
for (let i = 0; i < n.length; i++) {
if (n[i] == '0') {
if (temp && primeCheck(parseInt(temp))) {
cnt++;
}
temp='';
}
else {
temp+=n[i];
}
}
if (temp && primeCheck(parseInt(temp))) {
cnt++;
}
return cnt;
}