Kakao 2022 Blind Test - Lv2. k진수에서 소수 개수 구하기 (Java)

문제 요약

양의 정수 n을 k진수로 바꿨을 때, 변환된 수 안에 10진수 기준 소수가 몇 개인가?

 

[제한 조건] P는 소수

• 0P0처럼 소수 양쪽에 0이 있는 경우
• P0처럼 소수 오른쪽에만 0이 있고 왼쪽에는 아무것도 없는 경우
• 0P처럼 소수 왼쪽에만 0이 있고 오른쪽에는 아무것도 없는 경우
• P처럼 소수 양쪽에 아무것도 없는 경우
  • 예를 들어 숫자가 222인 경우, 숫자를 분해하여 소수를 판별하지 않음 = 소수가 아닌 수
• 단, P는 각 자릿수에 0을 포함하지 않는 소수
  • 예를 들어, 101은 P가 될 수 없음

 

[입출력]

1. n: 양의 정수 (1 ≤ n ≤ 1,000,000)
2. k: k진수 (3 ≤ k ≤ 10)

n	k	result
437674	3	3

---

문제 접근 

자세한 접근 법은 코드의 주석을 확인하세요 🙂

// 22. 06. 03. 금 - 카카오 2022 블라인드 - Lv.2 - k 진수에서 소 개수 구하기

public class Solution {
    public static void main(String[] args) {
        System.out.println(solution(437674, 3));
    }

    public static int solution(int n, int k) {
        int answer = 0; // 소수의 개수

        // ** 양의 정수 n을 k진법의 수로 만든다.
        //  - 양의 정수 n을 k진법의 수로 만들면서 나머지가 0이기 전까지의 수가 소수인지 판별한다. 단 1은 제외한다.
        String base_k = "";
        int remainder = 0;
        while (n >= k) {
            remainder = n % k;
            if (remainder == 0) {
                if (!base_k.isEmpty() && Integer.parseInt(base_k) != 1) {
                    if (isPrime(Long.parseLong(base_k))) answer++;
                }
                base_k = "";
            } else {
                base_k = remainder + base_k;
            }
            n /= k;
        }
        if (isPrime(Long.parseLong(n + base_k))) answer++;

        return answer;
    }

// 소수의 자릿수가 int의 범위를 넘어설 수 있기 때문에 long type으로 인자받기
    private static boolean isPrime(long n) {
        for (long i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) return false;
        }
        return true;
    }
}

---

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/92335

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