[완전탐색] 프로그래머스 소수 찾기 level2 자바 (Java)

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

프로그래머스

문제 설명

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

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

제한 조건

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

입출력 예

"17"	3
"011"	2

풀이

1. 종이조각으로 만들 수 있는 모든 숫자를 구한다.

2. 해당 숫자가 소수인지 검사한다.

 

완전탐색에는 아래와 같은 기법이 있는데 나는 1번 부분을 구현하기 위해 dfs방법을 사용했다.

 - 단순 Brute-Force

 - 비트마스크(Bitmask)

 - 재귀 함수

 - 순열 (Permutation)

 - BFS / DFS

 

소수를 구하는 방법은 2부터 자기자신을 나눴을때 나누어 지지 않는다면 소수이다.

 

코드

import java.util.*;
class Solution {
    boolean []checked = new boolean[10];
    ArrayList<Integer> arr = new ArrayList<>();
    
    public int solution(String numbers) {
        int answer = 0;
        
        String tmp = "";
        for(int i = 0; i < numbers.length(); i++){
            dfs(numbers, tmp, i+1);
        }
        for(int i = 0; i < arr.size(); i++){
            if(arr.get(i) == 0) continue;
            if(arr.get(i) == 1) continue;
            boolean flag = false;
            for(int j = 2; j < arr.get(i) ; j++)
                if(arr.get(i) % j == 0) {
                    flag = true;
                    break;
                }
            if(flag == true) continue;
            answer++;
        }
        return answer;
    }


    public void dfs(String str, String tmp, int m){
        if(tmp.length() == m){
            int num = Integer.parseInt(tmp);
            if(!arr.contains(num))
                arr.add(num);
            return;
        }
        else{
            for(int i = 0; i < str.length(); i++){
                if(!checked[i]){
                    checked[i] = true;
                    tmp += str.charAt(i);
                    dfs(str, tmp, m);
                    checked[i] = false;
                    tmp = tmp.substring(0, tmp.length()-1);
                }
            }
        }
    }
}