2022 KAKAO BLIND RECRUITMENT > k진수에서 소수 개수 구하기 - JAVA

 

 

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

풀이 - 나의 생각

 

1. 주어진 int n을 K진수로 바꾸기

2. 조건에 맞춰 숫자 자르기

3. 그 숫자가 소수인지 확인하기

 

1은

 

Integer.toString(int n, int k)

-> n을 k진수로 변환하여 String 형으로 반환한다.

 

2는

 

String.split("0+")

-> 0 또는 연속된 0을 기준으로 문자열을 분환해줌

 

3은

 

에라토스테네스의 체를 활용했는데

 

원래는 n까지 소수의 개수를 찾는 방식이지만

 

이번에는 n이 소수인지 아닌지 판별하는 방식으로 사용했다.

 

 

코드

 

import java.util.*;

class Solution {
    public int solution(int n, int k) {
        String converted = Integer.toString(n, k);
        String[] nums = converted.split("0+"); // 0 또는 연속된 00을 기준으로 분할
        
        int answer = 0;
        
        for(String s : nums){
            if(isPrimeNumber(s)){
                answer++;
            }
        }
        
        
        return answer;
    }
    
    public static boolean isPrimeNumber(String s){ //에라토스테네스의 체 활용
        long num = Long.parseLong(s);
        if(num <= 1){
            return false;
        }
        
        for(int i = 2; i <= Math.sqrt(num); i++){
            if(num % i == 0){
                return false;
            }
        }
        
        return true;
    }
}

 

 

 

 

 

 

 

다음에 또 봐요