[프로그래머스] Lv.2 소수 찾기 : 자바(Java)

문제 설명

 

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

각 종이 조각에 적힌 숫자가 적힌 문자열 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은 같은 숫자로 취급합니다.

 

풀이 방법

 

- 주어진 String numbers를 순열로 쪼개 각각이 소수인지 확인하기

- 중복된 숫자를 카운팅하지 않도록 HashSet 사용

- recur 백트래킹으로 순열 조회 (근데 더 깔끔한 백트래킹 있을 것 같음........)

- isPrime 소수인지 확인하기. N이 소수라면 약수를 N과 1만 갖고 있으므로 2 ~ N-1로 N을 다 나눠봤을 때 나머지가 하나라도 0이 아니라면 N은 소수가 아님. 근데 0이나 1이 들어올 수 있으니까 그냥 false처리 해주기  

.. 이제 생각이 든 건데 그냥 먼저 리턴해주면 되는구나 ㅇㅋ

 

알고리즘 머리가 굳은 것 같음... 아니 굳었음

  

 

import java.util.*;

class Solution {
    
    static char[] numberList;
    static boolean[] visited;
    static String num;
    static Set<Integer> set;
    
    public int solution(String numbers) {
        int answer = 0;
        set = new HashSet<>();
        for(int i = 1; i <= numbers.length(); i++){
            numberList = new char[i];
            visited = new boolean[numbers.length()];
            recur(0, i, numbers, numberList);
        }
        Iterator<Integer> iter = set.iterator();
        while(iter.hasNext()){
            if(isPrime(iter.next())) answer++;
        }
        return answer;
    }
    
    static boolean isPrime(int N){
        boolean res = true;
        for(int i = 2; i <= N - 1; i++){
            if(N % i == 0) {
                res = false;
                break;
            }
        }
        if(N == 0 || N == 1) res = false;
        return res;
    }
    
    
    static void recur(int idx, int n, String numbers, char[] numberList){
        if(idx == n){
            num = "";
            for(int i = 0; i < n; i++){
                num += numberList[i];
            }
            set.add(Integer.parseInt(num));
            return;
        }
        
        for(int i = 0; i < numbers.length(); i++){
            if(!visited[i]){
                numberList[idx] = numbers.charAt(i);
                visited[i] = true;
                recur(idx + 1, n, numbers, numberList);
                visited[i] = false;
            }
        }
    }
}

 

더 좋은 풀이 많을게 분명