프로그래머스 - 소수 찾기

소수 찾기 문제가 여러개인 것 같던데 이 문제이다.(레벨2)

수를 조합 가능한 모든 경우의 수를 찾아봐야 하므로 백트래킹 알고리즘을 사용하였다.

그런데 다 풀고 보니 수를 모두 사용했을 때의 경우의 수가 아니라 수를 모두 사용하지 않아도 그냥 만들 수 있는 모든 경우의 수를 찾아야 했다.
예를 들면, 1과 7이 주어졌을 때 탐색해야 하는 경우는 17, 71 이 아니라 1, 7, 17, 71 인 것이다.
이 경우는 어떻게 해야 하는지 몰랐는데, 풀이는 다음과 같았다.

이전까지는 보통, 특정 길이가 됐을 때 처리로직을 수행하고 return시켰는데
이 경우에는, 다음 index에 대한 백트래킹 메서드가 실행되자마자 처리로직을 수행하고, 그 다음 특정 길이인지 검사한 후 return시키면 된다.
코드 참고

import java.util.*;
class Solution {
    static int[] nums;
    static int[] isUsed;
    static HashSet<Integer> set = new HashSet<>();
    public int solution(String numbers) {
        int answer = 0;
        int length = numbers.length();
        nums = new int[length];
        isUsed = new int[length];
        for(int i = 0; i < length; i++){
            nums[i] = numbers.charAt(i) - '0';
        }
        //현재까지 사용한 index, 이전까지 사용해서 만든 숫자
        bt(0, "");
        Iterator<Integer> it = set.iterator();
        return set.size();
    }
    static void bt(int index, String str){  ////현재까지 사용한 index, 이전까지 사용해서 만든 숫자
        //특정 길이가 됐을 때가 아니라, 숫자가 추가 될 때 마다
        //소수인지 검사후 set에 add
        //이전까지 만든 숫자가 ""가 아니면 && 이전까지 만든 숫자가 소수면
        if(!str.equals("") && isPrimeNum(Integer.parseInt(str))){
            //이전까지 만든 숫자를 Set에 add
            set.add(Integer.parseInt(str));
        }
        //주어진 숫자를 모두 사용했으면 return
        if(index == nums.length){
            return;
        }
        for(int i = 0;i < nums.length; i++){
            if(isUsed[i] == 1){
                continue;
            }
            isUsed[i] = 1;
            bt(index+1, str+nums[i]);   //index++, 숫자하나를 추가한 후 다음 bt()실행
            isUsed[i] = 0;
        }
    }
    static boolean isPrimeNum(int n){
        //n이 0이거나 1인 경우 return false안해주면 아래 반복문을 지나쳐서 true를 반환하게 됨
        if(n == 0 || n == 1){
            return false;
        }
        //2부터 n-1사이의 수 중 n의 약수가 존재하는지(n을 나눌 수 있는 수 가 있는지)
        for(int i = 2; i < n; i++){
            if(n%i == 0){
                return false;
            }
        }
        return true;
    }
}

마지막에 놓친 부분

• 소수를 판별하는 isPrimeNum()메서드에서, 넘어온 n이 0이거나 1인 경우에 대해서 처리해주어야 함

참고한 사이트
https://hu-coding.tistory.com/132