[프로그래머스/자바] k진수에서 소수 개수 구하기 풀이 - 2022 KAKAO BLIND RECRUITMENT

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

프로그래머스

 

2022 KAKAO BLIND RECRUITMENT Level 2 문제다.

 

 

 

처음엔 조건에 맞는 소수라고 하니 꽤나 복잡해보였다.

주어진 숫자를 k진수로 변환 후, 0을 기준으로 잘라 소수인지 판별하면 된다.

 

예시를 보면 0을 기준으로 자르기만 하면 간단한 문제임을 알 수 있다.

437674 -> 211020101011 -> 211, 2, 1, 1, 11 -> 211, 2, 11 -> 3개

 

처음엔 에라토스테네스의 체 를 사용하려고 배열을 최대로 설정했는데,

1번과 11번 테스트 케이스를 계속 틀렸다. (런타임 에러)

k진수로 변환 시 int 범위를 벗어나는 큰 값이 나올 수 있는데

이를 배열로 처리하려고 해서 런타임 에러가 뜬게 아닐까 싶다.

(자바의 배열 크기는 int의 범위만큼만 할당할 수 있다.)

 

그래서 그냥 0으로 자른 값 하나하나 소수를 판별하는 메소드 isPrime()에 전달하는 방식으로 변경했다.

런타임 에러를 피하기 위해 0으로 자른 값을 long으로 변환해야 한다.

 

에라토스테네스의 체를 사용하지 않더라도

1부터 n까지 나누어지는 값이 있는지 확인하지 않고,

2부터 루트n까지 검사하는 방식으로 구현해 효율성을 높였다.

 

간단한 문제인데 괜히 어렵게 생각해서 시간만 잡아먹었다..ㅎㅎ

 

 

import java.util.StringTokenizer;

class Solution {
    
    public int solution(int n, int k) {
        String str = Integer.toString(n, k);
        
        StringTokenizer st = new StringTokenizer(str, "0");
        
        int cnt = 0;
        
        while(st.hasMoreTokens()) {
            if(isPrime(Long.parseLong(st.nextToken())))
                cnt++;
        }
        
        return cnt;
    }
    
    static boolean isPrime(long n) {
        if(n == 0 || n == 1)
            return false;
        
        if(n == 2)
            return true;

        for(long i=2;i<=Math.sqrt(n);i++)
            if(n % i == 0)
                return false;
        
        return true;
    }
}