[알고리즘] 2022 KAKAO BLIND k진수에서 소수 개수 구하기 (Java)

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

프로그래머스

 

조건에 따르면, 0을 기준으로 구분하여 만들어진 숫자 중 소수가 몇 개인지 구분해야 한다.

 

N을 K진수 String으로 변환한 뒤, StringTokenizer를 통해 소수인지 여부를 확인하는 식으로 구현했고,

 

N을 K진수로 변환할 때 Integer.parseInt(N,K)를 활용하는 방식 또한 있는데,

 

해당 문제를 풀 때 그 방식을 깜빡하여(...) K진수 변환을 직접 구현했다.

 

또한 소수 판정을 하는 효율적인? 방식에는 크게 두 가지가 있는데,

 

이 문제의 경우 소수의 길이가 최대 100만일 수 있기 때문에 에라토스테네스의 체를 사용하지 않고

 

확인해야 할 수의 제곱근까지 약수가 존재하는 지 여부를 확인하는 방식을 사용했다.

 

 

import java.io.*;
import java.util.*;
import java.math.*;

class Solution {
    static int cnt;
    public String decimalToKth(int num,int k){
        int check = 1;
        int N = num;
        
        while(N/check>=1){
            check *= k;
        }
        check /= k;
        
        //n은 mul자리수인 k진수
        
        String kthnum = "";
        N = num;
        
        while(check >= 1){
            if(N > 0){
                kthnum += Integer.toString(N/check);
                N %= check;
            }
            else{
                kthnum += Integer.toString(0);
            }
            check /= k;
        }
        
        return kthnum;
    }
    
    public static void findPrime(Long num){
        if(num == 1){
            return;
        }
        for(int i=2;i<=Math.sqrt(num);i++){
            if(num%i == 0){
                return;
            }
        }
        
        cnt++;
    }
    
    public int solution(int n, int k) {
        cnt = 0;
        
        String KthNum = decimalToKth(n,k);
        
        if(!KthNum.contains("0")){
            findPrime(Long.parseLong(KthNum));
        }
        else{
            StringTokenizer st = new StringTokenizer(KthNum,"0");
            
            while(st.hasMoreTokens()){
                findPrime(Long.parseLong(st.nextToken()));
            }
        }
        
        return cnt;
    }
}