[프로그래머스 코딩테스트] 소수 만들기(Java)

  문제 설명

  주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요.

 

  제한사항

• nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다.
• nums의 각 원소는 1 이상 1,000 이하의 자연수이며, 중복된 숫자가 들어있지 않습니다.

 

  입출력 예

nums	result
[1, 2, 3, 4]	1
[1, 2, 7, 6, 4]	4

class Solution {
    public int solution(int[] nums) {
        int answer = -1;
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        int[] array = new int[sum + 1];
        for (int i = 2; i <= sum; i++) {
            array[i] = 1;
        }
        for (int i = 2; i <= (int)Math.sqrt(sum); i++) {
            if (array[i] == 0) {
                continue;
            }
            int num = i * 2;
            while (num <= sum) {
                array[num] = 0;
                num += i;
            }
        }
        for (int i = 0; i < nums.length - 2; i++) {
            for (int j = i + 1; j < nums.length - 1; j++) {
                for (int k = j + 1; k < nums.length; k++) {
                    int sum2 = nums[i] + nums[j] + nums[k];
                    if (array[sum2] == 1) {
                        answer++;
                    }
                }
            }
        }
        return answer + 1;
    }
}

  변수 sum을 생성합니다.

  첫 번째 for문이 nums의 길이만큼 순회합니다.

  sum에 nums의 i 번째 원소를 더하기 할당합니다. 이는 에라토스테네스의 체 알고리즘을 이용하여 소수를 한 번에 판별하기 위함입니다. 정렬하여 마지막 세 원소를 더하여 최댓값을 구하고 싶었으나 시간이 더 오래 걸리는 탓에 모든 원소를 더해주었습니다. 만약 원소의 수가 아주 많다면 정렬한 뒤 계산하는 것이 유리해 보입니다.

  배열 array를 생성합니다. 0번 인덱스를 사용하지 않기 때문에 크기는 sum에 1을 더한 값으로 지정합니다.

  두 번째 for문이 2부터 sum까지 순회합니다.

  array의 i 번째 원소에 1을 할당합니다.

  세 번째 for문이 2부터 sum의 제곱근까지 순호합니다.

  if문에서 array의 i 번째 원소가 0이라면 continue로 넘어갑니다.

  변수 num을 생성하고 i에 2를 곱한 값을 할당합니다. 이는 i가 배수인지 확인하는 것입니다.

  while문은 num이 sum보다 작거나 같은 동안 반복합니다.

  num은 소수가 아니므로 array의 num 번째 원소에 0을 할당합니다.

  num에 i를 더하기 할당하여 i의 모든 배수를 걸러줍니다.

  세 번의 중첩 for문으로 세 수의 합을 구할 것입니다. 바깥 for문은 0부터 nums의 길이 - 2만큼 순회합니다. 중간 for문은 i + 1부터 nums의 길이 - 1만큼 순회합니다. 안쪽 for문은 j + 1부터 nums의 길이만큼 순회합니다.

  변수 sum2를 생성하여 세 수의 합을 담습니다. 각각 nums의 i, j, k 번째 원소입니다.

  if문에서 array의 sum2 번째 원소가 1이라면 소수라는 뜻입니다.

  answer가 증가합니다.

  문제에서는 answer를 -1로 초기화하고 있으므로 반환하기 전 1을 더해줍니다.

 

  소수 찾는 법에 대한 자세한 설명

  [프로그래머스 코딩테스트] 소수 찾기(Java) https://sigfriede.tistory.com/114