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

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

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

 

[ 풀이 ]

 

1. 숫자 n 을 k진법의 문자열로 변환한다.

 

2. 문자열을 "0"을 기준으로 각각의 문자열로 쪼개어 배열에 담는다.

•  이 때 배열에 공백이 들어갈 수 있다. 예를 들어 문제에 나온 예제 2번의 경우 k 진법으로 변환된 문자열이 110011 인데 이를 0을 기준으로 문자열들을 배열에 담으면 "11" , "" , "11" 이 들어가게 된다. 그렇기 때문에 각 배열에 들어간 값이 소수인지 판별하기 전에 배열의 값이 공백인지 아닌지 먼저 확인한다.
• 공백이 아닌 경우 배열의 문자를 10진법의 숫자로 다시 변환한 뒤 소수인지 판별한다. 소수가 맞다면 answer 값을 증가시킨다.

이 때, 10진법의 숫자로 변환시킬 때 주의해야할 점은 바로 long 형의 숫자로 변환시켜야 한다는 것이다.

처음에는 int 형으로 변환 시킨 후 코드를 제출하였더니 몇몇 케이스에서 런타임 오류가 발생하였다. 원인을 생각해보니 k진법으로 변환시키게 되면서 문자열이 대단히 길어질 수가 있다는 점이다. 그렇게 되면 문자열을 잘라서 10진법으로 변환 했을 때 int형의 범위를 초과할 수 있게 된다.

 

[ 전체 코드 ]

class Solution {
    public int solution(int n, int k) {
        int answer = 0;
        String jinsu = Integer.toString( n , k );	// k진법의 문자열로 변환        
        String[] nums = jinsu.split("0");	// 0 기준으로 문자열을 쪼갠다.   
        for( int i = 0 ; i < nums.length ; i++ ){            
            if( nums[i].equals("") ) continue;
            if( isSosu( Long.parseLong( nums[i] ) ) ) answer++;
        }        
        return answer;
    }
    
    // 10진법의 숫자가 소수인지 판별하는 함수
    static boolean isSosu( long num ){
        if( num == 1 ) return false; 	// 1은 소수가 아니므로 제외    
        
        //소수인지 판별
        for( long i = 2 ; i <= Math.sqrt( num ) ; i++ ){
            if( num % i == 0 )return false;
        }
        return true;
    }
}