[프로그래머스] k진수에서 소수 개수 구하기

문제

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

프로그래머스

 

문제 분석

 

주어진 n 을 k 진수로 바꾼 후 문제에서 제공하는 조건에 맞는 수 P 중 소수가 몇 개인지 계산하는 문제이다.

 

 

제한사항

• 1 <= n <= 1,000,000
• 3 <= k <= 10

n의 크기가 생각보다 크니 계산을 하다 int 크기를 넘어갈 수 도 있겠다는 생각이 들었다.

 

문제 접근

우선 주어진 n 을 k 진수로 만들기 위해 n을 k로 나눠가며 나머지 값을 붙여 k 진수 문자열을 만들었다.

 

k 진수 문자열을 0 기준으로 나누게 되면 P 배열을 얻을 수 있고 

 

P 값들 중 소수인 P를 판별하여 count 해준다.

 

여기서 계산을 하다보면 P 값이 int 크기를 초과할 수 있다.

 

 

코드

import java.util.*;

class Solution {
    public int solution(int n, int k) {
        int result = 0;
        StringBuffer sb = new StringBuffer();

        while(n != 0){
            sb.insert(0, n % k);
            n /= k;
        }


        String[] splits = sb.toString().split("0");

        List<Long> numList = new ArrayList<>();

        for (String numStr : splits) {
            if (!numStr.equals("")) {
                numList.add(Long.parseLong(numStr));
            }
        }

        for (long num : numList) {
            if (isPrime(num)) {
                result++;
            }
        }
        return result;
    }
    
    public static boolean isPrime(long num){
        if(num == 1){
            return false;
        }
        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }
}