k진수에서 소수 개수 구하기(Lv.2)

 

---

 

문제 설명

 

 

 

입출력 예시

 

 

요약

k진수에서 조건에 맞는 소수 개수 구하기

 

---

 

풀이

 

접근 방식

1. 10진수 n을 k진수로 변환

  → 진수 변환 메소드 trans()를 만들어 변환

 

2. 조건에 맞는 소수 개수 구하기

  → P는 각 자릿수에 0을 포함하지 않기 때문에 0을 기준으로 split 후 소수 판별

  → isPrime() 메소드를 통해 판별

 

---

 

코드리뷰

 

import java.util.*;

class Solution {
    String str = "";
    // 진수변환 메소드
    public void trans(int n, int k) {
        boolean run = true;
        List<String> list = new ArrayList<>();
        while(run) {
            list.add(0, String.valueOf(n % k));	// 나눈 나머지를 list에 담는다.
            n /= k;	// 나눈 몫을 n에 담는다.
            if(n == 0) {
                list.add(0, String.valueOf(n % k));	// 몫이 0일 때까지 나머지를 list의 0번째 index에 담아준다.
                run = false;
            }
        }
        for(String s : list) {
            str += s;	// 순서대로 문자열에 합친다.
        }
    }
    // 소수 판별 메소드
    public boolean isPrime(long num) {	// k진수 숫자의 자릿수가 클 수 있기 때문에 Long type으로 선언
        boolean result = true;
        if(num == 0 || num == 1) {
            result = false;	// 0과 1은 소수에서 제외
        } else {
            int limit = (int)Math.sqrt(num);	// 에라토스테네스의 체를 사용해 제곱근까지만 나눗셈 실행
            for(int i = 2; i <= limit; i++) {
                if(num % i == 0) {
                    result = false;	// 나머지가 0인 경우가 생기면 소수에서 제외
                    break;
                }
            }
        }
        return result;
    }
    
    public int solution(int n, int k) {
        trans(n, k);
        String[] arr = str.split("0");	// 변환된 문자열 형태의 k진수를 0을 기준으로 split

        int answer = 0;
        for(String num : arr) {
            // 0이 연속해서 존재하는 경우 빈 문자열이 포함되기 때문에 !num.isBlank()조건 추가
            if(!num.isBlank() && isPrime(Long.parseLong(num))) {	// 진수변환을 하게 되면 자릿수가 커져 int 범위를 넘어가기 때문에 Long으로 parsing
                answer++;
            }
        }
        return answer;
    }
}