[레벨1] 소수 만들기 (JAVA)

• 입력 배열의 최대 크기가 50 인 문제.
• 3개의 숫자를 3중포문을 이용해 선택(시간복잡도 n^3) + 소수인지 판별하는 함수(시간복잡도는 log(n)) = 최종적으로 O(n^3logn)의 시간복잡도를 갖는다.

class Solution {
	// 소수인지 판별하는 함수 O(logn)
    public static boolean isPrimeNumber(int n){
        
        for(int i=2; i<=Math.sqrt(n); ++i){
            if(n % i == 0)
                return false;
        }
        return true;
    }
    
    public int solution(int[] nums) {
        int answer = 0;

        // 3개의 숫자 선택 O(n^3)
        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){
                    if(isPrimeNumber(nums[i]+nums[j]+nums[k])){
                        answer++;
                    }
                }
            }
        }
        return answer;
    }
}