[201109] 소수 만들기 - Summer/Winter Coding(~2018) (level2)

0. 문제 유형 : 조합(완전탐색, 재귀), 소수(에라토스테네스의 체)
1. 문제 이해

(1) 주요 요구사항

- nums : 숫자들이 들어가 있는 배열

- nums 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 return

(2) 제한사항

- nums의 길이 : 3개 이상 50개이하 → 완전탐색 가능

- nums의 원소 : 1이상 1000이하 → 3개 수의 합 < 3000, int형 사용 가능

- nums의 원소 : 중복된 숫자 없음 → 중복 조합 상황 고려X

 

 

2. 전략

(1) 소수 판단 : public boolean[] calcPrime(int n)

- 나올 수 있는 소수의 범위 : 3000보다 작음

▶ 3000까지의 수에 대해 에라토스테네스의 체로 소수 구하기

- 에라토스테네스의 체

esw-csmoon.tistory.com/entry/200510-%EC%86%8C%EC%88%98-%EC%B0%BE%EA%B8%B0-%EC%97%B0%EC%8A%B5%EB%AC%B8%EC%A0%9C?category=1125729

① 소수 여부를 체크할 수 있는 boolean 배열(prime)을 하나 관리

② 2부터 순차적으로 배수인 경우 boolean 배열의 값을 true로 변경

③ false인 경우만 소수에 해당

 

(2) 각 조합에 대해서 소수인지 확인 : public void calculate(int[] nums, int n, int k, int level, int target, int sum)

- 조합 구하기, 종료 조건에 소수 확인 과정 추가

esw-csmoon.tistory.com/entry/%EC%88%9C%EC%97%B4%EC%A1%B0%ED%95%A9-%EC%99%84%EC%A0%84%ED%83%90%EC%83%89?category=1125729

① target번째 수의 선택 여부 결정 (단, target의 index가 n보다 작을 때까지만)

- 선택한다면? : sum에 nums[target] 추가

② target을 옮겨서 재귀 호출 (조합이므로 더이상 앞의 수들은 고려X - 이미 선택여부가 끝난것!!)

③ k가 0이 되면 sum이 소수인지 prime 배열을 통해 확인, 맞다면 answer값 증가

 

 

3. 참고사항

(1) 소수 확인 과정

: 각 경우의 수에 대해서 2~Math.sqrt(n) 까지의 수를 나누는 방법도 있음

▶ 경우의 수가 적은 경우는 더 유리, 경우의 수가 많고 수가 큰 경우에는 반복계산으로 인한 시간 증가

 

(2) 시간 복잡도 : 

 

 

4. 코드

class Solution {
    public boolean[] prime;
    public int answer;
    public int solution(int[] nums) {
        answer = 0;
        prime = calcPrime(3000);
        calculate(nums, nums.length, 3, 0, 0);
        return answer;
    }
    
    public void calculate(int[] nums, int n, int k, int target, int sum){ //visited 필요? - sum으로 대체, 시간복잡도줄임
        if(k == 0){
            if(!prime[sum]) answer++;
        }
        else{
            if(target < n){
                calculate(nums, n, k, target+1, sum);
                calculate(nums, n, k-1, target+1, sum+nums[target]);
            }
        }
    }
    
    public boolean[] calcPrime(int n){
        boolean[] result = new boolean[n+1];
        result[0] = true; result[1] = true;
        for(int i = 2; i <= Math.sqrt(n); i++){
            if(!result[i]){
                for(int j = 2; i*j < n+1; j++){
                    result[i*j] = true;
                }
            }
        }
        return result;
    }
}