[프로그래머스] k진수에서 소수 개수 구하기 - 자바(Java)

문제 링크

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

프로그래머스

 

 

문제 설명

양의 정수 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

 

 

입출력 예 설명

입출력 예 #1

문제 예시와 같습니다.

 

입출력 예 #2

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

 

 

코드

import java.util.Arrays;

class Solution {
    public int solution(int n, int k) {
        // 숫자 n을 k진법으로 표현한 문자열
        String kNumber = Integer.toString(n, k);
        // 문자열을 0을 기준으로 분리하여 배열에 저장
        String[] arr = kNumber.split("0");
        // 소수의 개수를 저장하는 변수
        int answer = 0;

        // 분리된 문자열 배열을 순회
        for (String s : arr) {
            if (s.equals("")) { // 빈 문자열 무시
                continue;
            }

            // 문자열을 long 타입 숫자로 변환합니다.
            long num = Long.parseLong(s);

            // 변환된 숫자가 소수인지 확인
            if (isPrime(num)) {
                answer++; // 소수인 경우 answer 증가
            }
        }

        return answer;
    }
    
    // 소수인지 여부를 판단하는 메서드
    private static boolean isPrime(long num) {
    	// 1보다 작거나 같은 경우 false
        if (num <= 1) {
            return false;
        }
        
        // i를 2부터 num의 제곱근 까지 반복
        for (int i = 2; i <= (int) Math.sqrt(num); i++) {
            // num % i가 0이면 소수가 아니므로 false 반환
            if (num % i == 0) {
                return false;
            }
        }
        
        return true;
    }
}

코드 설명

주석 참고

• 입력받은 정수 n과 k를 활용하여 숫자 n을 k진수로 변환하여 0을 기준으로 분리한 뒤, 분리된 숫자들 중에서 소수의 개수를 찾는 문제다.
• 먼저 입력받은 정수 n을 k진수로 표현하기 위해 Integer.toString(n, k)를 통해 얻은 후 kNumber 변수로 초기화한다.
• k진수로 변환된 kNumber를 split() 메서드를 통해 0을 기준으로 분리하여 문자열 배열 arr로 초기화한다.
• 소수의 개수를 저장하기 위한 변수 answer를 0으로 초기화한다.
• 분리된 문자열 배열 arr을 순회하여 각 요소가 소수인지 판별한다. 만약, 현재 문자열이 빈 문자열("")인 경우 무시한다.
• 빈 문자열이 아닌 경우, long 타입으로 변환하고 변환된 숫자가 소수인지 판별한다.
• 소수인 경우 answer를 증가시키고 아닌 경우 넘어간다.
• isPrime() 메서드는 소수인지 판별하기 위한 메서드로 소수인 경우 true를 반환하고, 그렇지 않은 경우 false를 반환한다.