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

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

🙋‍♂️ 들어가며

이번 문제는 백트랙킹과 소수 판별식을 활용하는 문제다

✅ 코드

class Solution {
    static int answer;
    static int N;
    
    public int solution(int[] nums) {
        answer = 0;
        N = nums.length;
        back_tracking(0, 0, 0, nums);
        return answer;
    }
    
    
    static void back_tracking(int idx, int cnt, int sum, int[] nums) {
        // 1. cnt 도달시 계산
        if (cnt == 3) {
            if (is_prime(sum)) {
                answer++;
            }
            return;
        }
        
        // 2. 가지치기 -> idx 초과 or (현재 고른횟수와 남은걸 다 골라도 3보다 작을때)
        if (idx >= N || cnt + (N-idx) < 3) return;
        
        
        // 3-1. 선택
        back_tracking(idx+1, cnt+1, sum + nums[idx], nums);
        
        // 3-2. 미선택
        back_tracking(idx+1, cnt, sum, nums);
    }
    
    
    // 4. 소수 판별식
    static boolean is_prime(int sum) {
        int res = 0;
        for (int i = 1; i < sum+1; i++) {
            if (sum % i == 0) res++;
        }
        
        if (res == 2) return true;
        
        return false;
    }
    
    
}

아차! 제출 후에 최적화가 가능한 것을 알 수 있었다

현재 내 소수 판별식은 O(N) 이지만 이렇게 변경 가능 -> O($\sqrt N$)

0, 1은 당연히 소수가 아니다.

2부터 시작인데 x의 약수는 $\sqrt x$ 의 약수와도 같다

그래서 제곱근인 $\sqrt x$ 으로 나누어지는지 보면 된다. -> 그렇다면 소수X

✅ (최적화) 코드

class Solution {
    static int answer;
    static int N;
    
    public int solution(int[] nums) {
        answer = 0;
        N = nums.length;
        back_tracking(0, 0, 0, nums);
        return answer;
    }
    
    
    static void back_tracking(int idx, int cnt, int sum, int[] nums) {
        // 1. cnt 도달시 계산
        if (cnt == 3) {
            if (is_prime(sum)) {
                answer++;
            }
            return;
        }
        
        // 2. 가지치기 -> idx 초과 or (현재 고른횟수와 남은걸 다 골라도 3보다 작을때)
        if (idx >= N || cnt + (N-idx) < 3) return;
        
        
        // 3-1. 선택
        back_tracking(idx+1, cnt+1, sum + nums[idx], nums);
        
        // 3-2. 미선택
        back_tracking(idx+1, cnt, sum, nums);
    }
    
    // 4. 소수 판별식
    static boolean is_prime(int sum) {
        // 4-1. 0, 1 처리
        if (sum < 2) return false;
        
        // 4-2. 하나라도 제곱근으로 나누어지면 소수가 아니다
        int i = 2;
        while (i*i <= sum) {
            if (sum % i == 0) return false;
            i++;
        }
        return true;
    }

    
    
}