[프로그래머스 JAVA] Lv2. 소수찾기

Lv2. 소수찾기

https://school.programmers.co.kr/learn/courses/30/lessons/42839

문제설명

주어진 정수를 K진법으로 변환한 후변화된 문자열에서 각 0으로 구분된 숫자가 소수인지 아닌지 판단

접근방식

O(log(n) * sqrt(log(n))) 시간복잡도

 

• Integer.toString(n, k) 메서드를 사용하여 n을 k진법으로 변환한다. O(log(n)) 시간이 소요된다.
•  
• isPrime 메서드는 문자열을 정수로 변환한 후, 소수 여부를 판별한다.
• 숫자가 num일 때, 소수 판별에는 O(sqrt(num))의 시간이 소요된다.
• 변환된 수는 log(n) 길이를 가지므로, 이 과정의 전체 시간 복잡도는 O(log(n) * sqrt(log(n)))이다.
•  
• 문자열을 0으로 분리하고 각 부분을 소수 판별한다.
• 이 과정의 시간 복잡도는 문자열의 길이에 비례한다.
• 문자열의 길이는 O(log(n))이므로 이 단계의 복잡도는 O(log(n) * sqrt(log(n)))다.

 

문제 조건 분석 과정

 

• 정수를 k진법으로 변환하여 문자열로 바꾼다.
• 변환된 문자열을 0을 기준으로 분리한다.
• 각 부분 문자열이 소수인지 판별한다.
• 소수인 경우에는 결과에 포함하지 않으며, 소수가 아닌 경우에는 결과를 증가시킨다.

 

전체코드

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) {
        int n = 437674; //변환할 수
        int k = 3; //변환할 진법 (3진법)

        //solution메서드 호출
        System.out.println(solution(n, k));
    }

    public static int solution(int n, int k) {

        int result = 0;
        //정수 n을 진법 k로 변환한 문자열
        String re = Integer.toString(n, k);

        //문자열을 0으로 구분하여 분리
        for(String rea : re.split("0")){
            //빈 문자열 무시
            if(rea.equals("")) continue;
            //문자열이 소수인지 확인
            if(isPrime(rea) == false){
                result++; //소수가 아닌 경우 result 증가
            }
        }

        return result;

    }

    public static boolean isPrime(String num){
        long n = Long.parseLong(num);

        //1은 소수가 아님
        if(n == 1){
            return true;
        }

        //2부터 n의 제곱근까지 나눠서 소수 여부 판별
        for(int i = 2; i <= Math.sqrt(n); i++){
            if(n % i == 0){
                return true; //나누어 떨어지면 소수가 아님
            }
        }

        return false;
    }
}