소수 만들기

문제정의

---

nums에 있는 수 중 3가지를 뽑아 그 합이 소수인 경우의 수를 출력하는 문제이다.

문제풀이

---

전체 코드는 다음과 같다.

package level2;

public class MakePrime {

    //프로그래머스 문제풀이 level2 소수 만들기
    public static void main(String[] args) {
        int[] nums = {1,2,3,4};
        int answer = ReturnPrimeCnt(nums, 0, 0, 3);
    }
    public static int ReturnPrimeCnt(int[] nums, int idx, int sum, int cnt)
    {
        if(cnt == 0)
        {
            for(int i = 2; i <= Math.sqrt(sum); i++)
            {
                if(sum % i == 0)
                    return 0;
            }
            return 1;
        }
        else
        {
            int res = 0;
            for(int i = idx; i <= nums.length-cnt; i++)
            {
                res += ReturnPrimeCnt(nums, i+1, sum+nums[i], cnt-1);
            }
            return res;
        }
    }
}

숫자 3개를 뽑는 재귀를 이용해 문제를 풀었다. ReturnPrimeCnt는 다음과 같이 동작한다. 1. 만약 cnt가 0이면 3개를 다 뽑았다는 의미이므로 소수인지 판별한다. 필자는 에라토테네스의 체를 활용해 시간을 단축했다. 소수면 1, 아니면 0을 반환한다. 2. 아직 숫자를 더 뽑을 수 있다면 idx부터 nums길이 - cnt까지 숫자를 모두 뽑아본다. 경우의수에서 가지를 쳐나가는 것과 비슷하다고 생각하면 된다. for문의 범위는 중복없이 수를 뽑을 수 있게 한것이므로 앞으로의 코딩에도 참고하면 많은 도움이 될 것이다.

이 함수는 3개만 아니라 4개, 5개로 영역을 뻗어나갈 수 있다. 하지만 속도가 좀 느릴 수 있다. 이 문제에선 오히려 3중 루프가 더 빠르다.

최종 시간복잡도는 3개 수를 뽑는 모든 수를 탐색하므로 \(O(n^3)\)이다.

테스트