[프로그래머스]JAVA 소수찾기 -완전 탐색

참고 :

  백트레킹 유튜브  : https://youtu.be/Enz2csssTCs?t=457 

 

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

프로그래머스

import java.util.*;
import java.util.stream.Collectors;

public class Solution {
  public int solution(String numbers) {
    int answer = 0;

    //초기값 세팅
    String[] split = numbers.split("");
    //변수 사용 현황
    boolean[] isUsed = new boolean[numbers.length()];
    Arrays.fill(isUsed, false);
    //변수 리스트화
    List<String> collect = Arrays.stream(split)
            .collect(Collectors.toList());
    //셋 초기화, 소수 중복 고려
    Set<Integer> primes = new HashSet<>();
    for(int i=0; i<numbers.length(); i++){
      backtrack(i, new StringBuffer(), collect,numbers.length(), isUsed, primes);
    }
      
    answer = primes.size();
    return answer;
  }

  //isPrime
  public boolean isPrime(int n) {
    if(n <= 1) return false;
    for(int j=2; j*j<n+1; j++){
      if(n%j==0) return false;
    }
    return true;
  }

  //backtracking
  public void backtrack(int depth, StringBuffer number, List<String> collect,int length, boolean[] isUsed, Set<Integer> primes){
    if(depth == length){
      //마지막 숫자 추출
      Integer fNumber = Integer.valueOf(number.toString());
      //소수 판별후 셋에 추가
      if(isPrime(fNumber)) primes.add(fNumber);
      return;
    }

    for(int i=0; i<length; i++){
      if(isUsed[i]) continue;
      isUsed[i] = true;
      backtrack(depth+1, new StringBuffer(number).append(collect.get(i)), collect, length, isUsed, primes);
      isUsed[i] = false;
    }
  }
}