[프로그래머스_Level2] 소수 찾기

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

프로그래머스

[문제]

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

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

 

[제한사항]

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

 

[코드]

import java.util.*;

public class Solution {
	static char[] num;
    static boolean[] visited;
    static int answer;
    static ArrayList<Integer> arr=new ArrayList<>();
    
    public static int solution(String numbers) {
        num=new char[numbers.length()];
        visited=new boolean[numbers.length()];
        
        // 문자열의 각 자리를 나눠 저장
        for(int i=0;i<numbers.length();i++)
            num[i]=numbers.charAt(i);
        
        // 자릿수를 늘려가며 조합 구하기
        for(int i=0;i<numbers.length();i++) {
        	 dfs(i,"");
        }
        
        // 소수 개수 count
        for(int i=0;i<arr.size();i++){
            if(isPrime(arr.get(i))) {
            	answer++;
            }
                
        }
        
        return answer;
    }
    
    // 소수 구하는 함수
    static boolean isPrime(int num) {
        if(num==0||num==1)
            return false;
        
        for(int i=2;i*i<=num;i++){
            if(num%i==0)
                return false;
        }
        
        return true;
    }
    
    // 조합 구하기
    static void dfs(int depth, String str){
        if(depth==num.length){
            // 문자열을 int로 변환한 값이 포함되어 있는지 확인해야 앞자리가 0인 문자열에서 0을 제외하고 삽입 가능
            if(!arr.contains(Integer.parseInt(str)))
                arr.add(Integer.parseInt(str));
            
            return;
        }
        
        for(int i=0;i<num.length;i++){
            if(!visited[i]){
                visited[i]=true;
                dfs(depth+1,str+num[i]);
                visited[i]=false;
            }
        }
    }
}

 

[고찰]

 이번 문제는 조합을 구하는 문제로 DFS 알고리즘을 사용해야 했다. 조합의 길이는 계속 달라지기 때문에 for문을 사용하여 조합의 길이를 변환해 주면서 재귀호출을 해주었다. 이때, 완성된 숫자를 연결리스트에 삽입할 때 맨 앞자리가 0인 것은 제거해주기 위해 문자열을 정수형으로 바꿔주는 과정이 필요하다.