소수 만들기 (프로그래머스) - Java

해결 방법

소수를 빠르게 구하기 위해 에라토스테네스의 채 방법을 적용하고 있으니, 궁금한 사람은 다음 링크를 먼저 참고하자.

소수 찾기 (프로그래머스) - Java

N개의 배열에서 3개의 숫자를 골라 더했을때 소수인지 구해야 한다. N개의 배열에서 3개의 숫자를 고르는 경우의수는 3^N에 근접한다. for문이 3개가 필요하므로 시간 복잡도는 O(3^N)이 될것이다. 때문에 모든 반복문 경우에서 소수를 일일이 구하는 방법은 시간효율성 면에서 엄청난 낭비이다. 

 

그렇기 때문에 에라토스테네스의 채 방법을 이용해 소수를 미리 구해놓고 경우의 수에 따라 1번의 인덱스 접근만으로 소수인지 아닌지 판별하도록 하는 것이 더 효율적이다.  

 

또 주의할 점이 있는데, 삼중 for문에서 초기값을 제대로 설정해줘야 한다. 그렇지 않으면 중복된 선택으로 인해 답이 더 많이 나오게 된다.   

 

구현 코드는 다음과 같다.

import java.util.Arrays;
import java.util.Collections;
import java.lang.Math;

class Solution {
    public int solution(int[] num) {
        int answer = 0;
        
        // java에서 내림차순 정렬을 위해 Integer 배열에 
        // 따로 담음
        Integer[] nums = new Integer[num.length];
        for(int i = 0; i < nums.length; ++i)
            nums[i] = num[i];
        
        // 먼저 내림차순 정렬
        Arrays.sort(nums, Collections.reverseOrder());
        
        // 배열 내에서 검사 가능한 최대 소수 범위
        int size = nums[0] + nums[1] + nums[2];
       
        // 최대 소수 범위 만큼에서 소수를 걸러내기 위한
        // boolean 배열
        boolean[] arrPrime = new boolean[size + 1];
        for(int i = 0; i < arrPrime.length; ++i)
            arrPrime[i] = true;
        
        // 에라토스테네스의 채 사용을 위해 
        // 제외한 배수 범위를 정해줌
        int limit = (int)Math.ceil(Math.sqrt(size)) + 1;
        
        // 소수가 아닌 배수를 제외 시킨다
        for(int i = 2; i < limit; ++i) {
            if(arrPrime[i]) {
                for(int j = i * i; j <= size; j += i) 
                    arrPrime[j] = false;
            }
        }
        
        // 중복되지 않게 숫자 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) {
                    int sum = nums[i] + nums[j] + nums[k];
                    if(arrPrime[sum]) ++answer;
                }
            }
        }
        
        return answer;
    }
}