2022 Kakao blind 92335 - k진수에서 소수 개수 구하기(진법변환, 소수판별, 문자열, 구현) - Java 풀이

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

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

- 주어진 정수n을 진법변환한 값의 부분문자열에서 0P0, P0, 0P, P 형태를 만족하는 소수가 몇개인지 카운트하면 된다.
n 최대값이 100만이므로 3진법으로 변환하면 1212210202001 이므로 변환시 long으로 처리해야한다. 
0이 존재하는지 Java의 String.contains(str) 혹은 C++의 find()를 std::string::find를 사용한다.
나머지는 조건에 맞게 순서대로 구현한다. 

- 구현내용이 긴 문제들은 순서대로 안하면 예외케이스 처리 등에서 실수가 많아지는 것 같다. 왠만하면 문제에서 제시된 조건 순서대로 구현하는 것이 좋은 것 같다.

import java.util.*;

class Solution {
    public int solution(int n, int k) {
        int ans = 0;
        StringBuilder sb = new StringBuilder();
        while(n > 0) {
            sb.append(n % k);
            n /= k;
        }
        sb = sb.reverse(); // 211020101011
        int N = sb.length();
        
        for(int i = 0; i < N; ++i) {
            for(int j = i + 1; j <= N; ++j) {
                String s = sb.substring(i, j);
                int len = s.length();
                
                if(len >= 3) {
                    if(s.startsWith("0") && s.endsWith("0")) { // 0P0
                        String s2 = s.substring(1, len-1);
                        if(!s2.contains("0") && isPrime(s2)) {
                            ++ans;
                        }
                    }
                }
                
                if(len >= 2) {
                    if(i == 0 && s.endsWith("0")) { // P0
                        String s3 = s.substring(0, len - 1);
                        if(!s3.contains("0") && isPrime(s3)) {
                            ++ans;
                        }
                    }
                    if(j == N && s.startsWith("0")) {
                        String s4 = s.substring(1);
                        if(!s4.contains("0") && isPrime(s4)) {
                            ++ans;
                        }
                    }
                }
                
                if(len == N && !s.contains("0") && isPrime(s)) ++ans;
            }
        }                
        
        return ans;
    }
    
    boolean isPrime(String s) {
        long n = Long.parseLong(s);
        if(n == 1) return false;
        for(int i = 2; i <= Math.sqrt(n); ++i) {
            if(n % i == 0) return false;
        }
        return true;
    }
}