[프로그래머스] 92335. k진수에서 소수 개수 구하기 JAVA

프로그래머스

---

 문제

양의 정수 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 함수를 완성해 주세요.

---

💝 예시

---

💝 풀이 설명

• Integer 클래스의 toString() 메서드를 이용하여 n을 k진수로 변환한다.
• 그리고 0을 기준으로 문자열을 나누어 배열에 대입한다.

public static int solution(int n, int k) {
   String s = Integer.toString(n, k);
   String[] target = s.split("0");
}

---

• 소수를 판별할 함수를 만들어준다.
• 2보다 작으면 거짓, 2면 진실, 그리고 제곱근을 이용하여 소수를 판별한다.

private static boolean is_Prime(long num) {
   if (num < 2) return false;
   if (num == 2) return true;

   for(int i = 2; i <= (int) Math.sqrt(num); i++) {
      if(num % i == 0) {
         return false;
      }
   }

   return true;
}

---

• 개수를 리턴할 값을 cnt로 선언하고, 초기화한다.
• 반복문을 돌면서 해당 숫자들이 소수인지 아닌지를 확인한다.
• 0을 기준으로 잘랐기에 0이 겹치는 경우 빈 문자열이 배열로 들어가기 때문에,  빈 배열이면 continue를 이용하여 다음 반복문으로 넘어가도록 하였다.
• 만약 소수이면 ( 소수면 참을 리턴하도록 하였음) 개수를 ++시켜준다.
• 그리고 카운트한 결과를 리턴해준다.

public static int solution(int n, int k) {
   
   ...
   
   int cnt = 0;
   for (int i = 0; i < target.length; i++) {
      if (target[i].equals("")) continue;
      long num = Long.parseLong(target[i]);
      if (is_Prime(num)) {
         cnt++;
      }
   }

   return cnt;
}

---

🦄 최종 풀이

public static int solution(int n, int k) {
   String s = Integer.toString(n, k);
   String[] target = s.split("0");

   int cnt = 0;
   for (int i = 0; i < target.length; i++) {
      if (target[i].equals("")) continue;
      long num = Long.parseLong(target[i]);
      if (is_Prime(num)) {
         cnt++;
      }
   }

   return cnt;
}
private static boolean is_Prime(long num) {
   if (num < 2) return false;
   if (num == 2) return true;

   for(int i = 2; i <= (int) Math.sqrt(num); i++) {
      if(num % i == 0) {
         return false;
      }
   }

   return true;
}​

---