[카카오] k진수에서 소수 개수 구하기 (java)

문제링크

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

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

문제풀이

👨🏻‍💻 핵심 스킬 👨🏻‍💻
  소수, 재귀

n으로 주어진 숫자를 k진수로 변경한 후 0을 오른쪽 또는 왼쪽으로 가지고 있는 수들이 소수인지 판단하여 개수를 구해주는 문제이다.

 

10진수인 n을 k진수로 변경하는 방법은 재귀와 나누기 그리고 %연산을 활용하여 만들 수 있다. %연산을 하여 구한 mod값을 앞쪽에 붙여주고, 나누기 연산을 해서 재귀적으로 돌려준다. 나누기 연산을 했을 때 그 값이 k보다 작게 된다면 k진수를 알맞게 구해준 것이라고 할 수 있다.

 

k 진수의 값을 구해주었다면, String의 split을 활용하여 0이 양옆으로 붙어있는 값들을 잘라내어준다. 그리고 그 값이 소수인지 확인하기 위해 2부터 %연산자를 활용해 나누어 떨어지는지(mod = 0) 계산한다. 이 때 2부터 소수인지 구하려고 하는 값까지 모두 체크해주는 것은 굉장히 비효율 적이기 때문에 그 값의 $√n$값 까지만 수행해주어도 된다.

 

2021.10.10 - [CordingTest/Algolithm] - 최대, 최소공배수 그리고 소수 소수를 구하는 방법을 알아보고 싶으면 왼쪽 링크를 확인해 주면된다.

 

에라토스테네스의 체로 구현을 하지 않은 이유는, 값이 Integer의 범위를 넘어가는 경우도 있기 때문이다.

 

구현코드

public class Solution {

    public int solution(int n, int k) {
        int answer = 0;
        String value = makeJinSu(n, k,"");
        String[] values = value.split("0+");

        for (int i = 0; i < values.length; i++) {
            if (values[i].equals("1"))
                continue;
            if (isPrime(Long.parseLong(values[i])))
                answer++;
        }
        return answer;
    }

    private boolean isPrime(long val) {
        if(val == 1L)
            return false;
        
        for (long j = 2; j * j <= val; j++) {
            if (val % j == 0) {
                return false;
            }
        }
        return true;
    }

    public String makeJinSu(int n, int k,String result) {
        if(n < k)
            return n%k+result;
        return makeJinSu(n/k,k,n%k + result);
    }
}

 

시간복잡도

소수를 구해주는 시간 $O(n/k)$  n의 값을 k로 나누어준 만큼 돌아주기 때문에

소수인지 체크해주기 위해 걸리는 시간은 $O(√n)$이 된다. 

잘못된 지식이나 궁금한 내용이 있을 경우 편하게 댓글 남겨주시면 감사하겠습니다 :)