[Programmers] 소수 찾기 - JAVA

📚 Problem

소수 찾기

• 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는가?
• "11" 과 "011" 은 같은 수로 취급합니다

📝 Solution

Key Idea

• 소수를 만드는 부분 과 소수를 판별하는 부분 두가지로 나누어 생각
• 소수를 만드는 부분에서는 DFS 와 check 배열[boolean]을 활용하여 순열을 구현해 문자열을 만든다
• 소수를 판별하는 부분에서는 만들어진 문자열을 숫자로 변환 하여 소수를 판별한다

    private ArrayList<Integer> answer = new ArrayList<>();
    private boolean[] check;
    public int solution(String numbers) {
        int length = numbers.length();
        char[] numAry = initAry(numbers);
        check = new boolean[length];

        make(numAry, length, "");

        return answer.size();
    }

💻 Code

Solution.java

import java.util.ArrayList;

class Solution {
    private ArrayList<Integer> answer = new ArrayList<>();
    private boolean[] check;
    public int solution(String numbers) {
        int length = numbers.length();
        char[] numAry = initAry(numbers);
        check = new boolean[length];

        make(numAry, length, "");

        return answer.size();
    }

    private char[] initAry(String numbers) {
        char[] numAry = new char[numbers.length()];

        for (int i = 0; i < numbers.length(); i++)
            numAry[i] = numbers.charAt(i);

        return numAry;
    }

    private void make(char[] numAry, int length, String numString) {
        if(!numString.equals("") && numString.length() <= length){
            int num = Integer.parseInt(numString);

            if(isPrimeNum(num) && !answer.contains(num))
                answer.add(Integer.valueOf(numString));

            if(numString.length() == length)
                return;
        }

        for(int i = 0; i < length; i++){
            if(!check[i]){
                check[i] = true;
                make(numAry,length,numString + numAry[i]);
                check[i] = false;
            }
        }
    }

    private boolean isPrimeNum(int num) {
        if(num == 0 || num == 1)
            return false;
        for (int i = 2; i < num; i++) {
            if(num % i == 0)
                return false;
        }
        return true;
    }
}

SolutionTest.java

import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.assertEquals;

public class SolutionTest {
    Solution solution;

    @BeforeEach
    public void setSol(){
        solution = new Solution();
    }

    @Test
    public void solution_1(){
        int result = solution.solution("17");
        assertEquals(3, result);
    }

    @Test
    public void solution_2(){
        int result = solution.solution("011");
        assertEquals(2, result);
    }
}