[JAVA] 프로그래머스 소수 만들기

문제를 처음보고 combination 문제라고 생각했다. 하지만 dfs방식을 구현하기보다 빠르게 구현하기 위해 완전탐색으로 구현해보았다.

 

완전탐색

class Solution {
    public int solution(int[] nums) {
        int answer = 0;

        for(int i=0; i<nums.length; i++){
            for (int j = 0; j < nums.length; j++) {
                for (int k = 0; k < nums.length; k++) {
                    if(i!=j && j!=k && i!=k){
                        int val = nums[i]+nums[j]+nums[k];
                        int count=0;
                        for(int s=1; s<val; s++){//소수판별
                            if(val%s==0) count++;
                        }
                        if(count==1) answer++;
                    }
                }
            }
        }

        return answer/6;
    }
}

 

아래는 dfs방식을 이용한 combintation 코드이다.

순열 조합에서

nCr = n-1Cr-1(현재 아이템 선택하지않은 경우) + n-1Cr(현재 아이템을 선택한 경우)

 

위 공식은 매우 중요하니 기억하자.

 

class Solution {
    int[] result = new int[3];
    int cnt = 0;
    int add = 0;
    int count;

    public int solution(int[] nums) {
        int answer = -1;

        comb(nums, nums.length, 3, 3);
        return count;
    }

    void comb(int[] nums, int n, int r, int q) {
        ++cnt;
        if(r == 0) {//3개를 모두 고르면 소수판별
            for(int n1:result) {
                add += n1;
            }
            boolean b = true;
            for(int i=2;i<add;i++) {
                if( (add%i) == 0) {
                    b= false;
                    break;
                }
            }
            if(b)++count;
            add = 0;//초기화
            return;
        }else if(n < r) {
            return;
        }else {//컴비네이션
            result[r-1] = nums[n-1];
            comb(nums, n-1, r-1, q);    //n-1Cr-1: 현재 아이템을 선택한 경우
            comb(nums, n-1, r, q);      ////n-1Cr: 현재 아이템을 선택하지 않은 경우
        }
    }
}