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

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

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

class Solution {
    public int solution(int n, int k) {
        int answer = 0;
        String s=kJinsu(n,k);
        String num="";
        for (int i=0; i<s.length(); i++){
            if (s.charAt(i)=='0'){
                if (num.length()>0){
                    long in=Long.parseLong(num);
                    if (isPrime(in)){
                        answer++;
                    }
                }
                num="";
            }
            else{
                num+=s.charAt(i);
            }
        }
        if (num.length()>0){
            long in=Long.parseLong(num);
            if (isPrime(in)){
                answer++;
            }
        }
        return answer;
    }
    
    public boolean isPrime(long n){
        if (n==1)
            return false;
        if (n==2)
            return true;
        for (long i=2; i*i<=n; i++){
            if (n%i==0){
                return false;
            }
        }
        return true;
    }
    
    public String kJinsu(int n, int k){
        String temp="";
        String s="";
        int q=-1;
        while (true){
            q=n/k;
            temp+=(char)((n%k)+'0');
            if (q==0){
                break;
            }
            n=q;
        }
        for (int i=temp.length()-1; i>=0; i--){
            s+=temp.charAt(i);
        }
        return s;
    }
    
}

코드를 깔끔하게 짜지 못한 것 같다..

 

일단 소수를 판별하는 알고리즘=>에라토스테네스의 체를 사용했는데, 계속 런타임 오류가 떴다.

보니까 범위를 계속 초과하는 듯했고, 최대 범위를 구하는 것도 뭔가 아닌 것 같아 보여 O(sqrt(n)) 인 소수 판별 알고리즘으로 대체했다.

2부터 sqrt(n) 값 까지 나누어 떨어지는지 검사하고, 그렇다면 소수가 아닌 걸로 판별하는 알고리즘이다. (isPrime 함수)

k진수를 구한 후 쭉 읽어가면서, 0이 아닌 수가 나타나면 문자열에 저장, 0이 나타나면 저장된 문자열들을 숫자로 바꾸고 소수인지 판별해주면 된다. 문자열을 저장하는 공간은 다시 초기화해준다.

 

k진수로 바꾸는 함수 kJinsu 에서, 나머지 값을 순차적으로 저장하다가 최종적으로 값을 뒤바꿔주는 로직으로 했는데, 이렇게 안해도 된다..

temp=(n%k)+temp 이런 식으로 해주면 가장 마지막 나머지가 앞에 오게 된다.

public static String kJinsu(int n, int k){
    String s="";
    while (n>0) {
        s=(n%k)+s;
        n/=k;
    }
    return s;
}

 

다른 분들의 코드를 보니, 다음과 같은 방법도 있었다. 

solution 함수에서 k진수를 읽어들일 때,

2중 for 문을 사용해 i번째 인덱스에서부터, 0이 나타날 때 그리고 범위를 넘기 전까지 수를 읽어준 뒤 소수를 판별하는 방법도 있다. substring을 이용해 (i,j) 로 문자열을 만들어주면 된다.