[92335] K진수에서 소수 개수 구하기

✔ K진수에서 소수 개수 구하기

[프로그래머스 92335]

문제 분석하기

n을 k진수로 변환한 후, 수를 살펴보며 조건에 맞는 소수가 몇 개 있는지 확인함

손으로 풀어보기

1. n을 k진수로 변환
2. 수가 조건에 맞다면 십진수로 변환하여 소수인지 확인
   • 이때 조건에 맞으려면 0을 기준으로 분리되므로 0으로 분리한 후 십진수로 변환하여 소수인지 확인
   • 이때 110011과 같이 0이 연속된 경우에는 공백으로 구성된 ""가 존재할 수 있으므로 이는 무시하도록 함
3. 조건에 맞는 소수의 갯수를 반환

슈도코드 작성하기

n(양의 정수)
k(진수)
answer(n을 k진수로 바꿨을 때, 변환된 수 안에서 찾을 수 있는 조건에 맞는 소수의 개수)
N(k진수로 변환한 n)
arr(N을 0을 기준으로 나눈 문자열 배열)
for(s -> arr만큼) {
    if(s가 공백이라면)
        continue;
    if(소수 확인하기 함수(s))
         answer 증가
}
answer 반환

소수 확인하기 함수 {
    origS(십진수로 변환한 s)
    if(origS가 1보다 작다면)
         소수가 아니므로 false 반환
     for(i -> 2부터 Math.sqrt(origS)까지) {
         if(origS가 i로 나누어진다면)
             약수가 있어 소수가 아니므로 false 반환
     }
     true 반환
}

코드 구현하기

/**
 * 92335) K진수에서_소수_개수_구하기
 */
public class L074_92335 {
    // n(양의 정수)
    // k(진수)
    public int solution(int n, int k) {
        // answer(n을 k진수로 바꿨을 때, 변환된 수 안에서 찾을 수 있는 조건에 맞는 소수의 개수)
        int answer = 0;
        // N(k진수로 변환한 n)
        String N = Integer.toString(n, k);
        // arr(N을 0을 기준으로 나눈 문자열 배열)
        String[] arr = N.split("0");
        for (String s : arr) {
            // s가 공백이라면
            if (s.equals(""))
                continue;
            // 소수 확인하기 함수(s)
            if (isPrime(s))
                // answer 증가
                answer++;
        }
        // answer 반환
        return answer;
    }

    // 소수 확인하기 함수
    private boolean isPrime(String s) {
        // origS(십진수로 변환한 s)
        Long origS = Long.parseLong(s, 10);
        // origS가 1보다 작다면
        if (origS <= 1)
            // 소수가 아니므로 false 반환
            return false;
        for (int i = 2; i <= Math.sqrt(origS); i++) {
            // origS가 i로 나누어진다면
            if (origS % i == 0)
                // 약수가 있어 소수가 아니므로 false 반환
                return false;
        }
        // true 반환
        return true;
    }

    // 테스트 케이스
    public static void main(String[] args) {
        L074_92335 solution = new L074_92335();

        int n = 437674;
        int k = 3;

        int result = solution.solution(n, k);

        System.out.println(result);
    }
}