[프로그래머스] 프로그래머스 Level2 k진수에서 소수 개수 구하기 Java (카카오 코딩테스트)

문제

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

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

풀이

소수 판별 + 문자열 구현 문제이다.

우선 매개변수 n을 k진수로 변환하여 문자열 변수에 담아주었고, 문자열의 루프를 돌면서 0이 아닐 때는 temp라는 임시 문자열 변수에 각 문자들을 더해주었고, 0을 만나면 temp를 Long으로 형변환 해주어 소수인지 판별할 수 있도록 해주었다.
하지만 예를 들어 0011이라는 값을 만나게 되면 루프를 돌다 마지막엔 0을 만나지 못해 형변환 -> 소수 판별의 사이클을 진행할 수 없으므로 i가 마지막 인덱스일 때는 따로 조건 처리 해주어 이때는 0을 만나지 않아도 소수인지 판별할 수 있도록 해주었다. 

문제를 풀면서 주의할 점은 첫 번째로 우리가 받는 매개변수의 타입은 int이지만 k진수로 형변환 하고 그것을 또 숫자로 형변환하기 때문에 int 자료형으로 값을 담지 못하는 오버플로우가 발생할 수 있다. 그렇기 때문에 Long형으로 계산할 수 있도록 해주어야 한다.

두 번째로 소수인지 판별할 때 시간복잡도가 O(n)인 코드로 소수인지 판별하게 된다면 우리가 받는 자료형이 Long이기 때문에 시간 초과가 날 수 있는 점을 잘 생각하여 에라토스테네스의 체를 사용하는 등 해서 소수 판별할 때 필요한 시간을 줄여줘야한다. 필자는 시간복잡도가 O(√N)인 코드로 시간 초과를 피할 수 있었다.

코드

+class Solution {
    public int solution(int n, int k) {

        int answer = 0;

        String str = Integer.toString(n, k);
        String temp = "";
        long param = 0;

        for(int i = 0; i < str.length(); i++) {

            if(str.charAt(i) != '0') {
                temp += str.charAt(i);
                if(i == str.length() - 1) {
                    param = Long.parseLong(temp);
                    if(isPrimeNumer(param)) {
                        answer++;
                    }
                }
            }
            else {
                if(temp.equals("")) {
                    continue;
                }
                param = Long.parseLong(temp);
                if(isPrimeNumer(param)) {
                    answer++;
                }
                temp = "";
            }
        }

        return answer;
    }

    boolean isPrimeNumer(long n) {

        if(n == 1) {
            return false;
        }

        for(long i = 2; i * i <= n; i++) {
            if(n % i == 0) {
                return false;
            }
        }
        return true;
    }
}