[프로그래머스] k진수에서 소수 개수 구하기 - JAVA

문제

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

프로그래머스

풀이

1. 주어진 n을 k진수로 나타내서 String에 담는다.
2. 설명이 길지만 결국 변환한 String 속에 0을 기준으로 구분되는 숫자들이 소수인지 판별해서 answer++ 해준다

그런데 테스트케이스에서 에러가 난다

왜 그런가 보니 1000000을 3진수로 바꾸면 int의 범위를 넘어간다. 따라서 parseLong을 이용하여 String 값을 long으로 변환해 줘야 한다.

 

하지만 이렇게 고쳤는데도 테스트케이스 1에서 시간초과가 발생했다.

isPrime 함수를 에라토스테네스의 체를 이용하여 구성하고자 했기 때문에 isPrime 함수 쪽 문제가 아닐거라 생각했는데 prime 함수 쪽의 문제였다(사실 문제인가 싶긴하다)

처음에 isPrime 함수를 다음과 같이 작성했다

 public boolean isPrime(long n){
    if(n==0 || n==1) return false;
    for(int i=2;i*i<=n;i++){
        if(n%i == 0)
            return false;
    }
    return true;
}

이렇게 작성했더니 시간 초과가 발생하여 i*i<=n을 i<=Math.sqrt(n)으로 변경했다.

그랬더니 테스트케이스 1을 통과했다.

이렇게 된 이유를 유추해보기로는 다음과 같다.

수학 그래프를 생각했을 때 x^2인 이차함수는 크기가 커지면 커질수록 가파르게 증가한다.

반면에 x^(1/2) 함수는 이차함수에 비해 완만하게 증가한다.

그러므로 매우 큰 숫자(예를 들면 1000000을 3진수로 나타낸 수)가 입력이 될 경우 x^2의 연산 시간이 더 오래걸려 시간초과가 발생하는 것이 아닌가 싶다.

 

아무튼 시간복잡도와 범위를 잘 생각해야 하는 문제였던 것 같다.

 

코드

import java.util.*;

class Solution {
    public int solution(int n, int k) {
        String temp = "";
        String str = "";
        
        int answer = 0;

        while(n > 0){
            temp += n % k;
            n = n/k;
        }
        for(int i=temp.length()-1;i>=0;i--){
            str += temp.charAt(i);
        }
        System.out.println(str);
        
        String num = "";
        for(int i=0;i<str.length();i++){
            if(str.charAt(i) == '0'){
                long number = Long.parseLong(num);
                if(isPrime(number)) answer+=1;
                num = "";
            }
            num += str.charAt(i);
        }
        long number = Long.parseLong(num);
        if(isPrime(number)) answer+=1;
        return answer;
    }
    
    public boolean isPrime(long n){
        if(n==0 || n==1) return false;
        for(int i=2;i<=Math.sqrt(n);i++){
            if(n%i == 0)
                return false;
        }
        return true;
        
       
    }
}