문제. k진수에서 소수 개수 구하기

문제 설명

양의 정수 n이 주어집니다. 이 숫자를 k진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 알아보려 합니다.

  • 0P0처럼 소수 양쪽에 0이 있는 경우
  • P0처럼 소수 오른쪽에만 0이 있고 왼쪽에는 아무것도 없는 경우
  • 0P처럼 소수 왼쪽에만 0이 있고 오른쪽에는 아무것도 없는 경우
  • P처럼 소수 양쪽에 아무것도 없는 경우
    • 단, P는 각 자릿수에 0을 포함하지 않는 소수입니다.

예를 들어, 101은 P가 될 수 없습니다.
예를 들어, 437674을 3진수로 바꾸면 211020101011입니다. 여기서 찾을 수 있는 조건에 맞는 소수는 왼쪽부터 순서대로 211, 2, 11이 있으며, 총 3개입니다. (211, 2, 11을 k진법으로 보았을 때가 아닌, 10진법으로 보았을 때 소수여야 한다는 점에 주의합니다.) 211은 P0 형태에서 찾을 수 있으며, 2는 0P0에서, 11은 0P에서 찾을 수 있습니다.

정수 n과 k가 매개변수로 주어집니다. n을 k진수로 바꿨을 때, 변환된 수 안에서 찾을 수 있는 위 조건에 맞는 소수의 개수를 return 하도록 solution 함수를 완성해 주세요.

제한사항

  • 1 ≤ n ≤ 1,000,000
  • 3 ≤ k ≤ 10

입출력 예

n k result
437674 3 3
110011 10 2

입출력 예 설명

입출력 예 #2

110011을 10진수로 바꾸면 110011입니다.
여기서 찾을 수 있는 조건에 맞는 소수는 11, 11 2개입니다.
이와 같이, 중복되는 소수를 발견하더라도 모두 따로 세어야 합니다.

1차 답안

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
import java.util.*;

class Solution {
    public int solution(int n, int k) {
        int answer = getPrimeList(n,k);
        return answer;
    }
    
    public static int getPrimeList(int n , int k){
        String answer = "";
        
        // k진수로 n 변경
        while (true){
            answer += n%k;
            n = n / k;
            // 목이 k 보다 아래라면
            if(n < k && n != 0) {
                answer += n;
                answer = new StringBuffer(answer).reverse().toString();
                break;
            }
        }

        // 규칙에 따르면 0을 기준으로 매핑이 되는것을 볼 수잇다. -> spilt("0"); 을통해 해당 영역의 크기 구해보자
        String [] answerList = answer.split("0");

        int max = Arrays.stream(answerList)
                    .filter(item -> !"".equals(item))   // filter -> 공백을 제거
                    .mapToInt(Integer::parseInt)
                    .max()
                    .getAsInt();

        // 에라토스테네스의 체를 기준으로 소수영역 빼오기
        boolean isPrime [] = new boolean[max + 1];

        Arrays.fill(isPrime, true);

        isPrime[0] = false;
        isPrime[1] = false;
        // 0, 1은 소수가 아니므로 false로 만듬

        for(int i = 2 ; i*i < isPrime.length ; i++) {
            if (isPrime[i])
                for (int j = 2; i * j < isPrime.length; j++)
                    isPrime[i * j] = false;
        }

        int count = 0;

        for(String answerFg : answerList){
            if(!"".equals(answerFg) && isPrime[Long.parseLong(answerFg)])
                count++;
        }

        return count;
    }
}

테스트케이스 1, 11에러
max 값 기준으로 에라토스테네스의 체를 구현했는데 배열로 선언되기 때문에 int 값 이상의 값이 들어올 경우를 계산하지 못햇다..
isPrime[int] 값으로 들어가는 영역에서 int값이외의 값이 들어온다면 overFlow가 되기때문에
int값이 아닌 Long 값으로 받는 경우가 생긴다.

2차답안

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
import java.util.*;

class Solution {
    public int solution(int n, int k) {
        int answer = getPrimeList(n,k);
        return answer;
    }
    
    public static int getPrimeList(int n , int k){
        String answer = "";
        
        // k진수로 n 변경
        while (true){
            answer += n%k;
            n = n / k;
            // 목이 k 보다 아래라면
            if(n < k && n != 0) {
                answer += n;
                answer = new StringBuffer(answer).reverse().toString();
                break;
            }
        }

        // 규칙에 따르면 0을 기준으로 매핑이 되는것을 볼 수잇다. -> spilt("0"); 을통해 해당 영역의 크기 구해보자
        String [] answerList = answer.split("0");

        int count = 0;

        for(String answerFg : answerList){
            if(!"".equals(answerFg) && is_prime(Long.parseLong(answerFg)))
                count++;
        }

        return count;
    }
    
    // 소수인지 확인 
    public static Boolean is_prime(Long number) {
        // 0 과 1 은 소수가 아니므로 종료
        if(number < 2) {
            return false;
        }

        // 2 는 소수
        if(number == 2) {
            return true;
        }

        for(int i = 2; i < Math.sqrt(number) + 1; i++) {
            // 소수가 아닐경우 종료
            if(number % i == 0) {
                return false;
            }
        }
        // 위 반복문에서 약수를 갖고 있지 않는경우 소수다.
        return true;
    }
}

만약 테스트케이스 14, 16 번에서 에러가 난다면
Math.sqrt(number) + 1이 부분을 탐색해보시면 좋을 것 같습니다.