[프로그래머스/Lv. 2] k진수에서 소수 개수 구하기 (JAVA)

🔺 문제

프로그래머스

 

 

🔺 코드

import java.util.*;
 
class Solution {    
    public int solution(int n, int k) {
        int answer = 0;
        String[] arr = Integer.toString(n, k).split("0"); // 진수 바꾸고 배열로 만듦
 
        for(String s : arr) {
            if(s.equals("")) continue; // 빈 문자열이면 패스
            
            long number = Long.parseLong(s);    // 오버플로우 방지 위해 long형 선언
            if(isPrime(number)){
                answer++;
            }
        }
        return answer;
    }
    
    // 소수 판별 메소드 (에라토스테네스의 체)
    public static boolean isPrime(long num){
        if(num == 1)    return false;
        
        for(int i = 2 ; i <= (int)Math.sqrt(num) ; i++){
            if(num % i == 0){
                return false;
            }
        }
        return true;
    } 
}

 

 

 

🧩 해결 아이디어

• 구현

- Integer.toString(n, k) ⇨ 10진수인 n을 k진수로 변환- 그러고 나서 0으로 분리해서 문자열 집합 만듦- 분리한 문자열이 빈 문자열이면, 패스. 빈 칸이 아니면 소수 판별 (에라토스테네스의 체 이용)

 

⚠ 소수 판별 함수의 받는 인자는 int형이 아닌 long형이어야 함

    (데이터 범위가 커서 진수 변경 시 int형 범위를 넘을 수 있기 때문)

 

---

🔺 다른 풀이들

- 십진법에서 다른 진법으로 변환하는 과정이 다르다.

[프로그래머스,자바] Level2: K진수에서 소수 개수 구하기

while(num != 0) {
    tmp = num % k + tmp;
    num /= k;
}

---

💬 느낀 점

자꾸 TC 1번만 시간 초과가 뜨길래 어이가 없었다....

알고 보니 소수 판별 메소드에서 에라토스테네스의 체 활용할 때

i <= Math.sqrt(num)이 아닌 i * i를 쓰면서 오버플로우가 발생해서 그런 것 같다.!!!!

 

문제를 파악했으니 진짜 문제 해결 완,....

 

시간 초과코드 확인하기

import java.util.*;
 
class Solution {
    public int solution(int n, int k) {
        int answer = 0;
        
        String[] str = Integer.toString(n, k).split("0");
        
        for(String s : str) {
            if(s.equals(""))    continue;
            
            if(isPrime(Long.parseLong(s)))
                answer++;
        }
        
        return answer;
    }
    
    static boolean isPrime(long num) {
        if(num <= 1)    return false;
 
        for(int i = 2 ; i * i <= num ; i++) {
            if(num % i == 0)
                return false;
        }
        return true;
    }
}

1회독	2회독	3회독	4회독	5회독
V	240203

---

(참고)

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