(Java) 프로그래머스 - k진수에서 소수 개수 구하기

처음 생각한 로직은 String을 k진법으로 변환후에 리스트를 선언해 맨 앞과 맨 뒤에 n을 추가한다.

다음으로 모든 조합을 만드는 메서드를 호출하고

문제에서 요구한 조건이 맞는지 확인하고 소수인지 판별하는 메서드를 호출하여

최종적으로 소수가 맞다면 answer을 증가 시키는것이었다.

그런데 문제를 너무 어렵게 생각해서 몇시간을 투자하고도 테스트 케이스 1,2 번을 맞추지 못했다.

결국 검색을 통해서 힌트를 얻었는데 생각보다 너무 간단했다.

 

P에 각 자리수에 0이 포함되어 있으면 안된다고 했으니

0을 기준으로 숫자를 나누어 소수인지 판별하기만 하면 된다.

 

---

실패 코드(테스트케이스 1, 2 실패)

import java.util.*;

class Solution {
    static String[] arr;
    static List<String> list;
    static int answer;
    public int solution(int n, int k) {
        answer = 0;

        // 진수 변환후 배열로
        arr = Long.toString(n, k).split("");

        // 양쪽을 체크하기 위해 list 생성
        list = new ArrayList<>();
        list.add("n");
        for (String s : arr) {
            list.add(s);
        }
        list.add("n");

        for (int i = 1; i < arr.length; i++) {
            com("", 1, i, 0);
        }

        return answer;

    }

    // 조합 생성 메서드
    static void com(String str, int idx, int cnt, int depth) {
        if (depth == cnt) {
            String result = list.get(idx - cnt - 1) + str;
            result += list.get(idx);
            check(result);
            return;
        }

        for (int i = idx; i <= arr.length; i++) {
            com(str + list.get(i), i + 1, cnt, depth + 1);
            if (!str.equals("")) {
                return;
            }
        }
    }

    // 조건 판별 메서드
    static void check(String result) {
        String prime = result.substring(1, result.length() - 1);
        char start = result.charAt(0);
        char end = result.charAt(result.length() - 1);
        if((start == 'n' && end == 'n') || (start == '0' && end == 'n') || (start == 'n' && end == '0') || (start == '0' && end == '0')) {
            if(!prime.contains("0")) {
                isPrimeNumber(prime);
            }
        }
    }
    
    // 소수 판별 메서드
    static void isPrimeNumber(String prime) {
        int n = Integer.parseInt(prime);
        if(n <= 1) {
            return;
        }
        boolean check = false;
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if(n % i == 0) {
                check = true;
                break;
            }
        }
        if(!check) {
            answer++;
        }
    }
}

 

최종 코드

import java.util.*;
class Solution {
    static int answer;
    public int solution(int n, int k) {
        answer = 0;

        // 진수 변환후 배열로
        String[] arr = Integer.toString(n, k).split("0");
        
        for (int i = 0; i < arr.length; i++) {
            // 빈 문자열이라면 통과
            if(arr[i].equals("")) continue;
            // 소수 판별 메서드 호출
            isPrimeNumber(arr[i]);
        }
        return answer;
    }
    // 소수 판별 메서드
    static void isPrimeNumber(String prime) {
        // 오버플로우 방지를 위해 long으로 선언
        long n = Long.parseLong(prime);
        // 1은 소수가 아니므로 return
        if(n <= 1) {
            return;
        }
        
        // 에라토스테네스의 채로 소수 판별
        boolean check = false;
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if(n % i == 0) {
                check = true;
                break;
            }
        }
        // 소수라면
        if(!check) {
            answer++;
        }
    }
}