2022 KAKAO BLIND RECRUITMENT - k진수에서 소수 개수 구하기 (JAVA)

❓ 문제 - 2022 KAKAO BLIND RECRUITMENT k진수에서 소수 개수 구하기 - JAVA 풀이법

출처 

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

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

 

 

📝 문제해결법 

1. 구현을 통해 문제를 해결하였다.

• 10진수 -> k진수로 변경은 String.valueof(바꾸려는 숫자(10진수), 바꾸려는 k진법) 로 간단하게 구현가능하다.
• k진수에서 split으로 0 형태로 분리된 값들을 String[] 배열에 넣어준다. 그러나 00이라는 경우에는 ""이 배열에 들어가므로 소수 판정 전에 한번 continue로 예외처리해준다.
• isPrime으로 소수 판정을 하는데 소수 판정할 숫자의 루트값을 씌워서 약수의 형태로 for문을 계속 돌리며 소수인지 판정한다.

2. 느낀점

• 처음에 계속 테케에서 런타임오류가 발생했는데... 알고 보니 소수 판정 전에 int형을 사용했다.
• 그러나 데이터 범위가 n이 1,000,000 까지 이므로 이것을 만약 2진수로 변경한다면 int형 배열보다 더 큰 숫자로 바뀔 수 있기 때문에 long 타입을 활용해야한다.
• 그리고 형변환 시에도 Long.parselong까지 적용시켜서 바꿔야 한다.
• 데이터 형 꼭 체크하자!!!!!!!!!!!!!!!!!!!!

 

 

💻 소스코드 

// 2022 KAKAO BLIND RECRUITMENT - k진수에서소수개수구하기
// 구현

import java.util.*;

class Solution2_LSH {
    public static void main(String[] args){
    }
    
    public int solution(int n, int k) {
        int answer = 0;
        String num = Integer.toString(n, k);
        String[] num_array = num.split("0");

        for(String s:num_array){
            if(s.equals("")) continue;
            long number = Long.parseLong(s);
            if(isPrime(number)){
                answer++;
            }
        }
        return answer;
    }
    
    public static boolean isPrime(long num){
        if(num == 1){
            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;
    }

    
    
}