[Programmers] 소수만들기 (Java)_Summer/Winter Coding(~2018)

# 출처 : https://programmers.co.kr/learn/courses/30/lessons/12977

코딩테스트 연습 - 소수 만들기

---

# 문제 요약

숫자들이 들어있는 배열 nums에 있는 숫자들 중, 서로 다른 3개를 골라서 더했을때 소수가 되는 경우의 개수를 return 하는 문제

 

# 풀이

backtracking 사용

시간복잡도 : O(N*3)

백트래킹? 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법

• 반복문의 횟수까지 줄일 수 있으므로 효율적
• 가지치기라고도 불리며, 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미

 

# 코드

class Solution {
    static final int sNum = 3;
    static int answer = 0;

    public static int solution(int[] nums) {
        final int numLength = nums.length;

        boolean[] visited = new boolean[numLength]; // false로 초기화
        combination(nums, visited, 0, numLength, 0, 0);

        return answer;
    }

    /**
     * 경우의 수
     * - 백트래킹 사용  
     * @param arr: 판별할 숫자 데이터_배열, 
     *        visited: 판별할 숫자 선택 여부_배열,
     *        start: 시작 위치,
     *        length: 배열 길이
     *        depth: 경우의 수(깊이)
     *        sum: 판별한 숫자들의 합
     */
    public static void combination(int[] arr, boolean[] visited, int start, int length, int depth, int sum){
        if(depth == sNum){ // sNum=3, 서로 다른 3개를 고를 경우 return
            // true: 소수이므로 카운팅, false: 소수가 아니므로 카운팅하지 않음
            answer += (primeIdentification(sum))? 1: 0; 
           return;
        }

        for(int i=start; i<length; i++) {
            visited[i] = true; // 판별할 숫자 선택 여부 표기
            combination(arr, visited, i + 1, length, depth + 1, sum + arr[i]);
            visited[i] = false; // 판별한 숫자 선택 여부 표기 취소
        }
    }

    /**
     * 소수 식별
     * - 제곱근까지만 판별 
     * @return true: 소수
     *         false: 소수아님
     */
    public static boolean primeIdentification(int num){
        // num=25라면, i=2~5까지만 판별
        for(int i=2; i*i<=num; i++){
            if(num % i == 0) return false;
        }
        return true;
    }
}