프로그래머스 | k진수에서 소수 개수 구하기 (Java)

🔒 문제

프로그래머스 Lv.2 2022 KAKAO BLIND RECRUITMENT k진수에서 소수 개수 구하기

🔑 해결

정수 n과 k가 매개변수로 주어지고, n을 k진수로 바꿨을 때 변환된 수 안에서 찾을 수 있는 위 조건에 맞는 소수의 개수를 return하는 solution함수를 작성하는 문제이다.

주의해야 할 점이 두 가지 있었다.
1. 조건에 맞는 P를 찾아 문자를 숫자로 형변환할 때, long을 사용해야 하는 것
2. 소수인지 판별할 때 i*i <= n을 사용하면 테스트케이스 1번에서 시간초과가 되기 때문에 Math.sqrt()함수를 사용해야 하는 것
이었다. 1번은 금방 알아차려 수정하였지만 2번을 알아내는 데에는 시간이 조금 걸렸다.

1. n을 k진수로 바꾸기
   1-1. n을 k진수로 바꿔 String형으로 반환하는 NtoK 함수를 만든다.
   1-2. n이 0이 될 때까지 Stringbuilder의 0번째 자리(제일 앞)에 n을 k로 나눈 나머지를 붙이고, n에 n을 k로 나눈 몫을 저장한다.
   1-3. while문을 다 돌았다면 Stringbuilder를 String형으로 바꾸어 return한다.
2. 조건에 맞는 P 찾기
   2-1. n을 k진수로 바꾼 nk를 0으로 split하여 String배열 ank에 저장한다.
   2-2. ank에 저장된 값 snk가 ""라면 continue
3. 소수 개수 찾기
   3-1. snk를 Long으로 형변환하여 lnk에 저장한다.
   3-2. 소수인지 판별하여 boolean값을 return하는 isPrime함수를 만들어, lnk가 소수인지 확인한다.
   3-3. n에 루트를 씌운 값만큼 i를 증가시키면서 n이 i로 나누어 떨어지는지 확인한다. 나누어 떨어진다면 false를 return한다.
   3-4. isPrime에서 반환된 값이 true라면 소수이므로 answer++

🔓 코드

class Solution {
    public int solution(int n, int k) {
        int answer = 0;
        
        // k진수로 바꾸기
        String nk = NtoK(n, k);
        
        // 조건에 맞는 P 찾기
        String[] ank = nk.split("0");
        
        for (String snk : ank) {
			if (snk.equals(""))
				continue;
			
			// 소수 개수 찾기
			long lnk = Long.parseLong(snk);
			if (isPrime(lnk))
				answer++;
		}
        
        
        return answer;
    }
    private boolean isPrime(long n) {
    	if (n == 1) {
            return false;
        }
        
    	for (int i = 2; i <= Math.sqrt(n); i++) {
			if (n % i == 0) {
				return false;
			}
		}
    	
    	return true;
    }
    
    private String NtoK(int n, int k) { // n을 k진수로 바꾸기
    	String nk = "";
    	StringBuilder sb = new StringBuilder();
    	
    	while(n != 0) {
    		sb.insert(0, n % k);
    		n = n / k;
    	}
    	
    	nk = sb.toString();
    	
    	return nk;
    }
}