[ DFS ] 프로그래머스 42839번 소수 찾기

DFS는 올 블루다

문제 설명

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

각 종이 조각에 적힌 숫자가 적힌 문자열 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은 같은 숫자로 취급합니다.

 

 

---

풀이과정

dfs로 숫자 조합을 만들고, 에라토스테네스의 체로 모든 소수를 찾은다음, 일치하는 개수를 구해야겠다고 생각함

1. numbers를 쪼개서 배열에 저장한다.
2. 숫자들의 모든 조합을 만들기 위해 길이를 1~numbers.length()로 각각 dfs를 돌린다.
3. dfs의 결과를 Set에 담아 중복을 제거한다. ( 앞자리에 0이 오는걸 없이개 위해 String으로 조합을 만들고 int형으로 바꾼다.)
4. numbers.length()만큼 9를 채워 배열이 만들어질 수 있는 최대값을 정하고,
5. 에라토스테네스의 체를 돌려서 최대값보다 작은 소수들을 모두 구한다. (prime함수)
6. set과 prime_list를 비교하여 total++를 해주고 출력

코드

import java.io.*;
import java.util.*;

class Solution {
    static String numbers; //입력값
    static int len; //numbers의 길이
    static boolean[] visited; //for DFS
    static ArrayList<Integer>  prime_list; //소수를 에라스토스테네스의 체로 만들어서 저장
    static Set<Integer> set; //조합할 수 있는 숫자들의 저장, 중복제거
    static int[] arr, arr_temp; //arr는 입력한 숫자들 따로따로 담고
                                //arr_temp는 dfs안에서 조합을 만들고, set으로 넘기기 전에
                                //조합을 임시로 저장할 배열
    static int max_len; //dfs를 길이별로 다르게 해서 돌렸음
                        //ex) 숫자가 3개면 max_len을 1,2,3으로 각각설정하여 dfs를 돌림

    public int solution(String numbers) {

        //numbers를 split하여 arr에 넣어줌
        len = numbers.length();
        arr = new int[len];
        String[] stemp = numbers.split("");
        for (int i = 0; i < len; i++) {
            arr[i] = Integer.parseInt(stemp[i]);
        }

        //dfs돌리기
        //len 만큼 max_len을 설정해줘서 슷자의 길이를 정해줌
        visited = new boolean[len];
        set = new HashSet<>();
        for (int i = 1; i <= len; i++) {
            max_len = i;
            arr_temp = new int[i];
            dfs(0);
        }

        //prime()으로 모든 소수를 구해서 prime_list에 저장
        //set과 prime_list에 저장
        int answer = 0; //정답을 담는곳
        prime_list = new ArrayList<>();
        prime(len);
        for (int i : set) {
            if (prime_list.contains(i)) {
                answer++;
            }
        }

//        System.out.println(answer);
        return answer;
    }
    //에라토스테네스의 체로 가능한 모든 소수 만들기
    static void prime(int len) {
        String s = "9".repeat(len);
        int max = Integer.parseInt(s);
        int[] check = new int[max + 1];
        for (int i = 2; i <= max; i++) {
            check[i] = i;
        }
        for (int i = 2; i <= max; i++) {
            if (check[i] != 0) {
                prime_list.add(i);
                for (int j = i * 2; j <= max; j += i) {
                    check[j] = 0;
                }
            }
        }
    }

    //dfs로 가능한 모든 숫자 조합 찾기
    static void dfs(int depth) {
        if (depth == max_len) {
            StringBuilder temp = new StringBuilder();
            for (int i : arr_temp) {
                temp.append(i);
            }
            set.add(Integer.parseInt(temp.toString()));
            return;
        }
        for (int i = 0; i < len; i++) {
            if (!visited[i]) {
                visited[i] = true;
                arr_temp[depth] = arr[i];
                dfs(depth + 1);
                visited[i] = false;
            }
        }
    }
}