Programmers - k진수에서 소수 개수 구하기(Java)

 

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

코딩테스트 연습 - k진수에서 소수 개수 구하기

 

풀이

해당 문제를 풀기위해서는 아래의 3단계가 필요함

1. k진수 변환
2. 0P0, P0, 0P, P의 수 찾기 -> 0을 기준으로 구분되는 수
3. 소수인지 확인

 

k진수 변환

주어진 입력 값을 k 진수로 변환

입력 값을 0이 될때까지 k로 나눈뒤 나머지를 String에 삽입

모든 삽입이 끝나면, String을 반대로 뒤집으면 K진수가 만들어짐

private static String convertKbinary(int n, int k) {
	StringBuilder str = new StringBuilder();

	while (n > 0) {
		str.append(n % k);
		n /= k;
	}
	str = str.reverse();
	
    return str.toString();
}

 

0으로 구분되는 수 찾기

0P0, 0P, P0, P의 형식이라고 복잡하게 설명되어 있지만, 결국 0으로 구분되는 수를 의미

 

i = 이전 탐색의 j위치

j = i+1 부터 시작하여 문자열의 끝이나 0일때까지 누적

int j = 0;

for (int i = 0; i < convertNum.length() - 1; i = j) {
	// covertNum[j]가 0을 만날때까지 또는 문자열의 끝까지
	for (j = i + 1; j < convertNum.length() && convertNum.charAt(j) != '0'; j++) ;
	// 0을 만났다면 i ~ j-1에 해당하는 수가 소수인지 판단
	if (isPrime(Long.parseLong(convertNum.substring(i, j)))) answer++;
}

 

소수인지 확인

 

소수 = 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수를 확인하기 위해서는 2개의 조건을 확인해야함

1. 1보다 큰 자연수인지

• 이는 단순히 매개변수의 값이 1이면 false로 처리 가능
• 단, 위의 0을 구분하는 방법으로는 j가 0을 만난위치가 다음 i의 위치이므로 "..00..."의 경우 '0'도 소수인지 탐색하는 경우가 발생

   -> 따라서, 같이 처리하기 위해 num <= 1를 조건으로 return false를 기입

 

2. 1과 자기 자신외의 수로 나눠지지 않는지

• 2 ~ num - 1까지의 수 중 나눴을 때 나머지가 0인 수가 있다면 소수가 아님
• 2 ~ num/2 까지의 수로 탐색 횟수를 줄여서 코드를 작성했으나 시간초과 발생

   num = a * b라고 할 때, a, b 두개의 값이 최소값이 되기 위해서는 a = b = √ num 이다.

    -> 따라서 2 ~ √ num까지의 수로 해결가능

private 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;
}

---

전체 코드

class Solution {
    public int solution(int n, int k) {
        int answer = 0;
        String convertNum = convertKbinary(n, k);

        int j = 0;
        for (int i = 0; i < convertNum.length() - 1; i = j) {
            for (j = i + 1; j < convertNum.length() && convertNum.charAt(j) != '0'; j++) ;
            if (isPrime(Long.parseLong(convertNum.substring(i, j))))
                answer++;
        }
        return answer;
    }
    
    private 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;
    }

    private static String convertKbinary(int n, int k) {
        StringBuilder str = new StringBuilder();

        while (n > 0) {
            str.append(n % k);
            n /= k;
        }

        str = str.reverse();
        return str.toString();
    }
    
}