프로그래머스(Lv.2) - k진수에서 소수 개수 구하기(Java)

 일단, k진수 결과물을 뽑아내야 하는데

String jinsu = "";
while(n > 0)
{
	jinsu += Integer.toString(n % k);
	n /= k;
}

방법은 이렇게 간단한 편이다. 나눈 나머지를 별도의 변수에다가 저장하면 되는데, 주의할 점은 저 문자열의 앞 뒤를 뒤집어야 진정한 k진수로 표현한 값이 나온다.

 

이렇게 구하고 나면 소수이고, 앞에 쓰여있는 조건을 만족해야 정답인데 보면 0을 기준으로 뭐 양쪽에 있다 한쪽에만 있다 거창하게 써놨지만, 간단하게 0을 기준으로 split을 해주면 모든 조건을 한 번에 만족시킬 수 있다.

 

그나마 효율성에서 걸릴만한 부분은 소수 판별 알고리즘인데

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

위의 함수로 소수 검사하고 싶은 숫자의 제곱근까지만 나머지 검사를 해주면 소수인지 아닌지 판별할 수 있다.

 

소수 검사에서 유명한 알고리즘으로는 에라토스테네스의 체가 있는데 이 알고리즘을 쓰고 싶다면

0으로 split 한 String 중의 최댓값을 구해서 boolean 배열의 범위를 설정해서 해줘야 하는데, 이 부분에서 문제가 발생하는 것이 int로 감당 안 되는 21억~~를 넘는 케이스가 나오기 때문에 boolean 배열을 선언하지 못한다. 즉, 이 문제에서 에라토스테네스의 체는 이용하지 못한다.

<문제>

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

프로그래머스

---

<소스코드>

class Solution {
    static boolean isPrime[];
    public int solution(int n, int k) {
        int answer = 0;
        
        String jinsu = "";
        while(n > 0)
        {
            jinsu += Integer.toString(n % k);
            n /= k;
        }
        
        /*
        소수를 구하고 뭐 0이 양쪽에 있는가 한 쪽에 있는가?라는 조건이 주렁주렁 달려있는데
        이는 0을 기준으로 스플릿을 해주면 간단하게 해결된다.
        */
        String[] arr = jinsu.split("0");
        
        for(String str : arr)
        {
            if(!str.equals(""))
            {
                StringBuilder sb = new StringBuilder(str);
                long num = Long.parseLong(sb.reverse().toString());

                if(isPrime(num)) answer++;
            }
        }
        return answer;
    }
    //간단한 소수판별 방법
    public static boolean isPrime(long n)
    {
        if(n < 2) return false;
        
        for(int i = 2 ; i <= Math.sqrt(n) ; i++)
        {
            if(n % i == 0) return false;
        }
        
        return true;
    }
}