이번에 풀어본 문제는
프로그래머스 k진수에서 소수 개수 구하기 입니다.

📕 문제 링크

❗️코드

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

        String parse = Integer.toString(n, k);
        String [] numbers = parse.split("0");

        for (String numberString : numbers) {
            // 0이 연속됐을경우 공백이 들어옴
            if (numberString.length() > 0) {
                if (isPrime(Long.parseLong(numberString))) answer++;
            }
        }
        return answer;
    }
    static boolean isPrime(Long num) {
        if (num <= 1) return false;
        
        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0) return false;
        }
        return true;
    }
}

📝 풀이

n을 k진수로 변경한 후, 주어진 조건에 맞는 0에 인접한 수들이 소수라면 카운트를 올려주고, 누적된 값을 반환하는 문제입니다. Integer.toString 함수를 사용하면 간단하게 진법 변환을 해줄 수 있습니다.
결과를 0을 기준으로 split 한 후, 남은 수들의 소수를 판별해주면 해결할 수 있습니다.
1번, 11번 테스트 케이스에서 런타임 에러가 나는 것으로 보아, int 범위를 벗어나는 것 같습니다. long 타입을 사용해주면 됩니다.

📜 후기

소수만 나오면 무조건 에라토스테네스의 체를 활용해서 풀었는데, 처음으로 벽에 막혔습니다.
이 문제같은 경우에는 int 범위를 벗어나는 값에 대해서도 소수 판별을 해주어야 하는데, 에라토스테네스의 체는 배열 인덱스를 통해 소수값을 담아놓고 판별하기 때문에 적용할 수 없었습니다.
특정 범위에 대한 소수판별이 아니라 이렇게 불규칙적으로 소수를 찾는 문제에서는 앞으로 위와 같은 방식을 사용해야할 것 같네요 ㅎㅎ