Programmers [소수 만들기] - 12977

문제는 다음 링크를 참고해주세요.

https://programmers.co.kr/learn/courses/30/lessons/12977

코딩테스트 연습 - 소수 만들기

 

nums 배열로부터 3개의 수를 골라 더하고, 그 값의 합이 소수인지를 판단하는 문제입니다.

이 문제의 포인트는 소수 판별과, 3가지 선택의 모든 경우의 수를 알맞게 구하는 것입니다.

 

우선 맨 먼저 해야할 일은 소수를 구하는 것입니다. 그래야 3개를 더한 값들이 소수인지 아닌지 판별할 수 있겠죠?

 

nums의 각 원소는 1~1000 까지의 자연수로, 중복된 숫자는 없습니다. 따라서 nums 3개의 값을 더했을 때 MAX = 998+999+1000 = 2997 입니다.

 

이제, 2997 까지의 자연수 중에서 소수를 모두 골라낼 것입니다.oddNum 이라는 변수에 소수를 담을 것입니다.

Arrays.sort(nums);
int[] arr = new int[2998];
List<Integer> oddNum = new ArrayList();

for(int i=2; i<arr.length; i++){ // 2 ~ 2997
    if(arr[i] == 0) {
        for (int j = 2 * i; j <= 2997; j += i) {
            if (arr[j] == 0){
                arr[j] = 1;
            }
        }
    }
}
for(int i=2;i<=2997;i++){
    if(arr[i] == 0)
        oddNum.add(i);
}

arr 이라는 배열 인덱스 값은 1 ~ 2997 까지 있습니다.

 

2부터 for문을 통해 배수를 지워나갑니다.

이 때 배수들은 1 로 방문했다는 표시를 해줍니다.

 

계속해서 저희는 arr[i] == 0 인 경우(방문하지 않은 경우) 에만 i의 배수를 지워나갈겁니다.

 

맨 마지막에 arr == 0인 경우가 소수이므로, 이를 oddNum 에 넣어줍니다.

 

oddNum 에 들어있는 값을 출력 해보면 아래와 같이 성공적으로 나옵니다.

 

> 2  3  5  7  11  13  17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97  101  103  107  109  113  127  131  137  139  149  151  157  163 ...... 2927  2939  2953  2957  2963  2969  2971

 

 

이제 nums에 있는 값을 3개씩 골라 더한 다음, 소수 판별을 해주면 끝입니다.

int n = nums.length;
for(int i=0; i< n-2; i++){
    for(int j=i+1; j< n-1; j++){
        for(int k=j+1; k< n; k++){
            int sum = nums[i]+nums[j]+nums[k];
            if(oddNum.contains(sum)){ // 세 수의 합이 소수
                answer++;
            }
        }
    }
}

 

 

전체 소스코드

public int solution(int[] nums) {
    int answer = 0;
    Arrays.sort(nums);
    int[] arr = new int[2998];
    List<Integer> oddNum = new ArrayList();

    for(int i=2; i<arr.length; i++){ // 2 ~ 2997
        if(arr[i] == 0) {
            for (int j = 2 * i; j <= 2997; j += i) {
                if (arr[j] == 0){
                    arr[j] = 1;
                }
            }
        }
    }
    for(int i=2;i<=2997;i++){
        if(arr[i] == 0)
            oddNum.add(i);
    }

    int n = nums.length;
    for(int i=0; i< n-2; i++){
        for(int j=i+1; j< n-1; j++){
            for(int k=j+1; k< n; k++){
                int sum = nums[i]+nums[j]+nums[k];
                if(oddNum.contains(sum)){ // 세 수의 합이 소수
                    answer++;
                }
            }
        }
    }

    return answer;
}