[Java] 프로그래머스 - 소수 찾기 (2단계)

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

 

코딩테스트 연습 - 소수 찾기

 

 

 

 

 

import java.util.*;
class Solution {
    ArrayList<Integer> nList; //추가한 숫자인지 확인용
    boolean[] check; //다녀간 숫자인지 확인용
    int answer; //리턴값 모을 용도
    public int solution(String numbers) {
        nList = new ArrayList<>();
        answer = 0;
        String[] temp = numbers.split("");
        int[] nums = new int[temp.length];
        check = new boolean[temp.length];
        
        //split으로 나눈 numbers를 int로 변경
        for (int i = 0; i < temp.length; i++) {
            nums[i] = Integer.parseInt(temp[i]);
        }
        
        func(nums, 0);
        
        return answer;
    }
    
    public void func(int[] nums, int num) {
        //무조건 체크하기
        if (checkNum(num)) {
            answer++;
            nList.add(num);
        }
        
       	//숫자 만들기
        for (int i = 0; i < nums.length; i++) {
            if (check[i]) continue;
            
            check[i] = true;
            int temp = num * 10 + nums[i];
            func(nums, temp);
            check[i] = false;
        }
    }
    
    //소수인지 체크하는 함수
    public boolean checkNum(int num) {
        if (num == 0 || num == 1) return false;
        if (nList.indexOf(num) != -1) return false;
        
        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0) return false;
        }
        
        return true;
    }
}

 

테스트 1 〉	통과 (0.22ms, 78.2MB)
테스트 2 〉	통과 (3.36ms, 72.3MB)
테스트 3 〉	통과 (0.13ms, 73.2MB)
테스트 4 〉	통과 (1.18ms, 72.6MB)
테스트 5 〉	통과 (2.58ms, 77.4MB)
테스트 6 〉	통과 (0.16ms, 78.5MB)
테스트 7 〉	통과 (0.34ms, 75.4MB)
테스트 8 〉	통과 (3.42ms, 86MB)
테스트 9 〉	통과 (0.23ms, 78.3MB)
테스트 10 〉	통과 (6.38ms, 74.1MB)
테스트 11 〉	통과 (1.26ms, 72.9MB)
테스트 12 〉	통과 (0.80ms, 69MB)