[Level1] 소수 만들기 JAV

내 풀이,, 완전 탐색 사용

class Solution {
    public boolean isPrime(int number) {
        for(int i=2; i<number; i++) {
            if(number % i == 0)
                return false;
        }
        return true;
    }
    
    public int solution(int[] nums) {
        int countPrime = 0;

        for(int i=0; i<nums.length; i++) {
            for(int j=i+1; j<nums.length; j++) {
                for(int k=j+1; k<nums.length; k++) {
                    int sum = nums[i] + nums[j] + nums[k];
                    if(isPrime(sum))
                        countPrime++;
                }
            }
        }
        return countPrime;
    }
}

 

소수를 판별할 때 시간 복잡도는 완전 탐색을 하기 때문에 O(N) 이다. 

다른 사람들의 풀이를 봤을 때 시간 복잡도를 O(N/2) 로 줄인 것을 봤는데

참고한 코드는 다음과 같다.

 

다른사람 풀이 (제곱근? 이용)

class Solution {
    public boolean isPrime(int number) {
        for(int i=2; i<= (int) Math.sqrt(number); i++) {
            if(number % i == 0)
                return false;
        }
        return true;
    }
    
    public int solution(int[] nums) {
        int countPrime = 0;

        for(int i=0; i<nums.length; i++) {
            for(int j=i+1; j<nums.length; j++) {
                for(int k=j+1; k<nums.length; k++) {
                    int sum = nums[i] + nums[j] + nums[k];
                    if(isPrime(sum))
                        countPrime++;
                }
            }
        }
        return countPrime;
    }
}