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

📚 문제 설명

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

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

제한 사항

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

🔎 입출력 예

예제 #1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

예제 #2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

• 11과 011은 같은 숫자로 취급합니다

💻 코드

import java.util.*;
import java.math.*;
class Solution {
    public HashSet<Integer> set;
    public boolean[] visited;
    public int solution(String numbers) {
        set = new HashSet<>();
        visited = new boolean[numbers.length()];
        dfs(0,0, numbers);
        int answer = 0;
        
        // 소수 찾기
        for(int s : set) {
            int count = 0;
            if(s < 2) continue;
            for(int i=2; i<=Math.sqrt(s); i++) {
                if(s % i == 0) {
                    count++;
                    break;
                }
            }
            
            if(count == 0) answer++;
        }
        return answer;
    }
    
    public void dfs(int num, int dept, String numbers) {
        set.add(num);
        if(dept == numbers.length()) return;
        
        for(int i=0; i<numbers.length(); i++) {
            if(!visited[i]) { //방문하지 않은 상태
                String str = Integer.toString(num) + numbers.charAt(i);
                visited[i] = true;
                dfs(Integer.parseInt(str), dept+1, numbers);
                visited[i] = false;
            }
        }
        
    }
}

📖 Solution

고민을 하다 이문제는 DFS로 풀어야할 것 같다고 생각을 했다.
아직도 DFS/BFS 문제는 어려운데 그래도 내가 풀었던 DFS 문제를 참고해서 풀 수 있었다. 언젠가는 바로 코드를 작성할 수 있기를 ... ☺

DFS를 사용해 set에 숫자가 적힌 종이 조각을 붙여서 만들 수 있는 모든 수를 담기로 하였다. 중복을 제거하기 위해 HashSet 사용!

그리고 한번 사용한 숫자는 사용하지 못하기 때문에 visited 배열을 이용하여 check해줬다.

마지막으로 set에서 소수를 찾아주면 끝!