[완전 탐색/Level2/Java] 소수 찾기

 문제 설명 

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

제한사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

입출력 예

numbers	return
"17"	3
"011"	2

입출력 예 설명

예제 #1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

예제 #2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

• 11과 011은 같은 숫자로 취급합니다.

 

 

 

---

처음 생각한 아이디어

1. answers의 문자열을 한글자씩 쪼개서 String [] c_arr 에 저장한다.

2. String[] c_arr 를 조합하여 가능한 모든 숫자 조합을 만들어 ArrayList에 저장한다.

3. ArrayList에 저장된 문자를 숫자로 parseInt하여 소수인지 판단하고, 개수를 센다.

 

였는데 2번에서 막혔다. 한글자씩 분리해서 어떻게 순열을 만드는지 잘 모르겠다. 

순열을 만들기위해서 depth뒤의 인덱스와 바꿔주는 swap방식을 써보았지만 실패했다.

결국 검색해서 어떻게 푸는지 아이디어만 ... 보기로 했다.

 

 

 

---

백트래킹

 DFS를 사용하여 만약 조건에 맞지 않으면 그 즉시 중단하고 이전으로 돌아가여 다시 확인하는 것을 반복하면서 원하는 조건을 찾는 알고리즘 

말은 쉬워보인다. 하지만 구현은..

 

눈물을 참고 이 문제에 백트래킹을 적용해보면 

numbers를 몇글자씩 조합할 건지 결정하고(i) , numbers 한글자씩을 붙여가면서 (j),  ArrayList 에 없는 숫자라면 집어 넣는 방식인 것 같다. 

몇글자씩 조합할 건지 결정하는 i의 범위는  1 ≤ i  ≤ numbers.length() 가 되겠다.

문제에서 numbers의 최대길이가 7이라 주어졌으니 numbers의 한글자당 방문 여부를 체크할 boolean 배열도 필요하다.

boolean[] visited = new boolean[7];

i =1 라면, numbers를 한 글자씩 쪼개서 넣는 것을 의미한다.

i=2 라면, numbers 중 두 글자씩 조합해서 넣는 것을 의미한다.

방문한 인덱스를 체크하고, 방문하지 않은 인덱스만  i 길이가 될 때까지 한글자씩 덧붙여 조합해가며 ArrayList에 넣어줄 함수 rec이다.

public static void rec(String numbers,String temp,int len);

매개변수 len으로 받는 것이 i 이다. 

자바에서 String 한글자씩 접근하려면 numbers.charAt(index); 이런식으로 접근해야한다.

 

 

 

---

최종 작성한 코드

import java.util.ArrayList;

//소수찾기
public class FindPrimeNumber2 {

	 static ArrayList<Integer> n_list = new ArrayList<>();
	 static boolean[] visited = new boolean[7];
	 
	public int solution(String numbers) {
		n_list.clear();
        int answer = 0;
        String str="";
        //2. 분리한 글자끼리의 모든 경우의 수 조합한 숫자 만들기
        for(int i=0;i<numbers.length();i++) {
        	rec(numbers,str,i+1);
        }
        //3. 조합한 숫자 중 소수찾아 카운트 증가
    	for(int i : n_list) {
    		int flag=0;
    		if(i==1||i==0) continue; // 1, 0 은 소수 검사 안함 
    		for(int j=2;j*j<=i;j++) {
    			if(i%j==0) { //소수아님 
    				flag=1;
    				break;
    			}
    		}
    		if(flag==0) {
    			answer++;
    		}
    	}

        return answer;
    }

	
	//2. 분리한 글자끼리의 모든 경우의 수 조합한 숫자 만들기
    public static void rec(String numbers,String temp,int len){
        // 10. 현재 만들고 있는 자릿수 == temp길이면 종료 
        if(temp.length() == len) {
            // 11. ArrayList에 이미 존재하는 값인지를 확인해 중복값 삽입을 방지
            if(!n_list.contains(Integer.parseInt(temp)))n_list.add(Integer.parseInt(temp));              
            return;
        }
        
        // 3. numbers를 탐색 (ex) numbers= "17" , len = 1
        for(int j =0;j<numbers.length();j++){
            // 4. 이미 방문한 인덱스면 패스
            if(visited[j]) continue;
            // 5. 임시 변수 temp에 붙여나가며 숫자를 조합 (ex) j=0 , temp = "1"; j=1, temp="7";
            temp += numbers.charAt(j);
            // 6. temp에 붙였기 때문에 방문처리
            visited[j] = true;
            // 7. 재귀, 앞서 붙인 temp변수와 현재 몇 자리의 수를 만드는지에 대한 정보인 len 변수를 전달
            rec(numbers,temp,len); // (ex) rec(numbers,"1",1);
            // 8. 조합이 완료되면 직전의 방문처리한 인덱스를 false로 변경
            visited[j] = false;
            // 9. temp 변수에서 마지막 자리의 숫자를 제외하고 갱신
            temp = temp.substring(0,temp.length()-1); //temp = "";
        }                      
    }
    
	
}