[Java] 소수 찾기 - Lv2 프로그래머스 완전탐색 - DFS / 코딩테스트 고득점 Kit

 

https://school.programmers.co.kr/learn/courses/30/lessons/42839

프로그래머스

 

 

풀이

---

1. DFS를 활용한 백트래킹을 통해 모든 경우의수 체크

2. 소수일 경우 중복을 거르기 위한 Set 사용

두가지를 메인으로 잡고 풀었다.

 

import java.util.*;

class Solution {
	
    static Set<Integer> set = new HashSet<>();
    char[] ch = new char[] {};
    boolean[] bl = new boolean[] {};


    public int solution(String numbers) {
        ch = numbers.toCharArray();
        bl = new boolean[ch.length];
        int idx = 0;

    	find("", 0);    	

    	return set.size();
    }

    void find(String word, int idx) {
        if(idx>ch.length) return;
        int num;
        if(word!="") {
        	num = Integer.parseInt(word);
        	if(primeCheck(num)) set.add(num);
    	}

        for(int i=0; i<ch.length; i++) {
            if(bl[i]) continue;
            bl[i]=true;
            find(word+ch[i], idx+1);    		
            bl[i]=false;
        }
    }

    private boolean primeCheck(int num) {
        if(num<2) return false;
        for(int i=2; i*i<=num; i++) {
            if(num%i==0) return false;
        }
        return true;
    }
}