Programmers / Level 1 / 소수 만들기

[문제설명]

주어진 숫자 중 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

 

import java.util.*;

class Solution {
    public int solution(int[] nums) {
        int answer = 0;
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }

        // 소수 구하기
        int[] arr = new int[sum + 1];
        for (int i = 2; i < arr.length; i++) {
            arr[i] = i;
        }

        for (int i = 2; i <= sum; i++) {
            // 2,3,5,7... 의 배수 빼기
            for (int j = 2 * i; j <= sum; j += i) {
                arr[j] = 0; // 소수 아닌 값 0으로 만들기
            }
        }

        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] != 0) { // 소수인 값들 배열에 넣기
                list.add(arr[i]);
            }
        }

        Arrays.sort(nums);
        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 n = nums[i]+nums[j]+nums[k];
                    for (Integer ans : list) {
                        if(ans==n) {
                            answer++;
                        }
                    }
                }
            }
        }
        System.out.println(answer);

        return answer;
    }
}

이전 소수 찾기 문제에서 한 방식과 비슷하게 코드를 짜봤다.

 

소수 만들기 문제는 주어진 nums배열의 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하는 것이다.

우선,  나올 수 있는 소수는 nums배열의 모든 값들을 합친 것 보다 작을 것이므로 그 합을 구해줬다 (sum)

 

그 후, 전의 포스팅에서 소수를 찾았던 것 처럼 에라토스테네스의 체를 사용해 소수인 값들을 list에 넣어주었다. 

   - 소수 찾기 포스팅 : https://gr616.tistory.com/254

 

nums배열의 3개의 숫자를 더했을 때 소수의 개수를 구하는 것이므로, for문을 돌며 3개의 값을 더한 값이

list에 있는지 검사하며 소수가 될 수 있는 경우의 개수를 구했다.

 

통과가 되긴 했지만, 몇몇 테스트 케이스가 시간이 꽤 오래걸렸고, 더 좋은 코드가 있을거라 생각돼 찾아봤다.

 

---

배열에서 3개의 수를 더하는 방식은 같았지만,

소수 찾기 함수를 만들어 더한 수를 전달해주고, 소수인지 판별해주는 방식이 훨씬 간단했다.

 

굳이 소수를 찾아 배열을 생성하고 비교해주지 않고,

우선 3개의 수를 더한 후, 그 수가 소수인 지 판별하는 방식이다.

 

import java.util.*;

class Solution {
    public int solution(int[] nums) {
       int answer = 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++) {
                    if(check(nums[i]+nums[j]+nums[k]) == true) { // 소수인 경우
                        answer++;
                    };
                }
            }
        }
        System.out.println(answer);

        return answer;
    }

    boolean check(int num) {
        for(int i=2; i<=Math.sqrt(num); i++) {
            if(num%i==0) {
                return false;
            }
        }
        return true;
    }
}

 

훨씬 빠르게 결과가 나오는 걸 볼 수 있다.

소수 찾기 알고리즘이 아직 좀 헷갈리는데, 능숙해져야 할 것 같다.