[프로그래머스] 소수 찾기 - JAVA, 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(깊이 우선 탐색)을 사용하여 풀이
• set 자료 구조를 사용하여 소수들을 저장하였는데 그 이유는 "011", "11"과 같이 다른 문자열이지만 같은 정수로 변환이 되는 경우 중복을 걸러내야 하기 때문이다.

import java.util.*;

class Solution {

    boolean[] visit; //탐색을 진행하면서 이미 사용한 숫자를 다시 사용하지 못하도록 확인하는 용도
    char[] arr; 
    Set<Integer> set = new HashSet<>();

    public boolean isPrime(int n) {
        if(n == 1 || n == 0) return false;

        for(int i = 2; i < n; i++) {
            if(n%i == 0) return false;
        }

        return true;
    }

    //char형 배열의 앞에서부터 length 길이 만큼 잘라서 int형으로 변환해서 반환
    public int charsToInt(char[] arr, int length) {
        StringBuilder sb = new StringBuilder();

        for(int i = 0; i < length; i++) {
            sb.append(arr[i]);
        }

        return Integer.parseInt(sb.toString());
    }

    public void dfs(int level, int length, String numbers) {
        if(level == length) {
            int num = charsToInt(arr, length);
            if(isPrime(num)) set.add(num);
        } else {
            for(int i = 0; i < numbers.length(); i++) {
                if(!visit[i]) {
                    visit[i] = true;
                    arr[level] = numbers.charAt(i);
                    dfs(level+1, length, numbers);
                    visit[i] = false;
                }
            }
        }
    }

    public int solution(String numbers) {
        visit = new boolean[numbers.length()];
        arr = new char[numbers.length()];

        for(int i = 1; i <= numbers.length(); i++) {
           dfs(0, i, numbers);
        }

        return set.size();
    }
}

문제 출처

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