[Java] 프로그래머스 - 소수 만들기 (1단계)

코딩 테스트 풀이 체크리스트
2시간 내에 풀었는가?	O
본인의 실력으로 풀었는가?	O

 

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

 

 

 

 

 

class Solution {
    
    boolean[] check;
    int answer;
    
    public int solution(int[] nums) {
        answer = 0;
        
        check = new boolean[nums.length];
        
        func(nums, 0, 0, 0);

        return answer;
    }
    
    public void func(int[] arr, int num, int index, int position) {
        if (index == 3) {
            boolean value = true;
            
            for (int i = 2; i < num; i++) {
                if (num % i == 0) {
                    value = false;
                    break;
                }
            }
            
            if (value) answer++;
            
            return;
        }
        
        for (int i = position; i < arr.length; i++) {
            if (check[i]) continue;
            
            check[i] = true;
            func(arr, num+arr[i], index+1, i+1);
            check[i] = false;
        }
    }
}

 

테스트 1 〉	통과 (0.62ms, 72MB)
테스트 2 〉	통과 (0.79ms, 73.3MB)
테스트 3 〉	통과 (0.28ms, 77.9MB)
테스트 4 〉	통과 (0.21ms, 77.4MB)
테스트 5 〉	통과 (0.99ms, 85.1MB)
테스트 6 〉	통과 (3.21ms, 69.6MB)
테스트 7 〉	통과 (0.28ms, 70.2MB)
테스트 8 〉	통과 (6.34ms, 75.1MB)
테스트 9 〉	통과 (0.78ms, 76.5MB)
테스트 10 〉	통과 (5.25ms, 78.5MB)
테스트 11 〉	통과 (0.07ms, 75.7MB)
테스트 12 〉	통과 (0.04ms, 72.4MB)
테스트 13 〉	통과 (0.06ms, 77.5MB)
테스트 14 〉	통과 (0.05ms, 72.9MB)
테스트 15 〉	통과 (0.03ms, 73.2MB)
테스트 16 〉	통과 (13.90ms, 79.4MB)
테스트 17 〉	통과 (0.63ms, 75.3MB)
테스트 18 〉	통과 (0.45ms, 71.1MB)
테스트 19 〉	통과 (0.06ms, 78.2MB)
테스트 20 〉	통과 (15.36ms, 76.8MB)
테스트 21 〉	통과 (14.37ms, 77.4MB)
테스트 22 〉	통과 (0.49ms, 76MB)
테스트 23 〉	통과 (0.02ms, 74.5MB)
테스트 24 〉	통과 (12.59ms, 76.1MB)
테스트 25 〉	통과 (12.55ms, 78.8MB)
테스트 26 〉	통과 (0.02ms, 76.8MB)

 

 

 

 

 

DP인가..? 어쨋든 하나씩 다녀오면서 숫자 3개를 더했는지 확인하고 더했으면 소수인지 확인 후 계산