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

 

문제는 프로그래머스 에서 찾을 수 있습니다. 

https://programmers.co.kr/

프로그래머스

 

 

풀이 : 

K 진수를 구하고 0이 나올 때 까지 문자열로 끊어서 체크하면 된다. 

 

다만 소수를 구하는 과정에서 에라토스테네스의 채를 생각하고 풀면 된다. 

int 형으로 할 경우 런타임 에러가 발생하는걸 보니 long으로 대체해서 풀었다. 

 

import java.util.*;

class Solution {
    public int solution(int n, int k) {
        int answer = 0;
        String knum = "";
        
        // k 진수 구하기
        while(true) {
            int mod = n % k;
            n = n / k;
            
            knum = mod + knum;
            
            if (n < k) {
                knum = n + knum;
                break;
            }
        }
            
        // 소수 구하기
        String target = "";
        
        for(int i = 0; i<knum.length(); i++) {
            if (knum.charAt(i) != '0') {
                target += knum.charAt(i);
            } else {
                if (target.contains("0")) {
                    target = ""; continue;
                } else {
                    if (target != "" && isPrimeNumber(Long.parseLong(target))) {
                        answer++;
                    }
                    target = "";
                }
            }
        }
        
        if (target != "" && isPrimeNumber(Long.parseLong(target))) {
            answer++;
        }

        return answer;
    }
    
    public boolean isPrimeNumber(long target) {
        if (target < 2) {
            return false;
        }
        
        if (target < 4) {
            return true;
        }
        
        for(int i = 2; i<=Math.sqrt(target) + 1; i++) {
            if (target % i == 0) {
                return false;
            }
        }
        return true;
    }
}