[프로그래머스/Lv.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

 

입출력 예 설명

입출력 예 #1
[1,2,4]를 이용해서 7을 만들 수 있습니다.

입출력 예 #2
[1,2,4]를 이용해서 7을 만들 수 있습니다.
[1,4,6]을 이용해서 11을 만들 수 있습니다.
[2,4,7]을 이용해서 13을 만들 수 있습니다.
[4,6,7]을 이용해서 17을 만들 수 있습니다.

 

 

⭕ 풀이

class Solution {
    public int solution(int[] arr) {
        int result = 0;
        boolean[] prime = new boolean[2997+1];
        for(int i=2;i<prime.length;i++) {
            prime[i] = true; 
        }
		
        for(int i=2;i*i<prime.length;i++) { // 에라토스테네스의 체
            for(int j=i*i;j<prime.length;j=j+i) {
                if(prime[i]) {
                    prime[j] = false;
                }
            }
        }
        
        for(int i=0;i<arr.length-2;i++) {  // 전체탐색
            for(int j=i+1;j<arr.length-1;j++) {
                for(int k=j+1;k<arr.length;k++) {
                    if(prime[arr[i]+arr[j]+arr[k]]) {
                        result++;
                    }
                }
            }
        }
        return result;
    }
}

 

개인적으로 소수관련 문제를 풀이할때 가능하다면 에라토스테네스의 체로 

소수가 아닌것들을 한번 다 거른뒤 풀이하는방법을 선호하므로 이번문제 역시 

첫번째 반복문에서는 boolean배열을 만들고 0,1을 제외한 2부터 true로 초기화를 수행했고

두번째 반복문에서는 소수가 아닌것들은 다시 false로 초기화하는 작업을 수행해주었다.

 

문제에서 입력되는 배열에서 원소의 중복은 없으며 최대값이 1000이하의 자연수였으므로

1000+999+998 이 2997로 최대값을 가질 수 있는 경우라서 2997+1을 배열의 길이로 산정하였다.

 

2998 길이의 배열을 만드는게 낭비라고 생각된다면

내림차순 정렬을 수행한뒤 arr[0]+arr[1]+arr[2] 로 최대값을 정해도 무방할것같다.

 

이렇게 소수가 true를 가지는 boolean배열이 완성됐다면 

숫자의 개수 3개를 사용해 소수를 만들어야 하므로 3중반복문을 수행하며

모두 더한값을 boolean배열의 인덱스로 사용하여 해당값이 true라면 소수라는뜻이므로 result를 1증가시킨다.

모든 경우의 수를 거친 뒤 최종연산된 result를 반환한다.

 

 

 

 

 

 

-출처

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