# Level 2 - 소수 찾기

[문제]

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

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

 

 

[내 풀이]

1. 종이 조각으로 만들 수 있는 가장 큰 수를 만든다.

2. 1번에서 만든 가장 큰수 사이의 소수를 모두 찾는다.

3. 2에서 찾은 소수들 중 종이 조각 모음으로 만들 수 있는 수를 찾는다.

 

문제 해결을 위해 위 방식으로 접근했었는데 이렇게하면 효율성 테스트를 통과하지 못한다...

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

class Solution {
    public int solution(String numbers) {
         int answer = 0;
        // 높은 순 정렬
        List<String> l = new ArrayList<>();
        for (int i = 0; i < numbers.length(); i++) {
            l.add(String.valueOf(numbers.charAt(i)));
        }
        l.sort((a,b)-> Integer.compare(Integer.parseInt(b),Integer.parseInt(a)));

        // 만들 수 있는 가장 큰 수
        StringBuilder sb = new StringBuilder();
        for (String s : l) {
            sb.append(s);
        }
        int max = Integer.parseInt(sb.toString()) +1;

        // 2~max 사이의 소수 구하기
        boolean[] p = new boolean[max];
        for (int i=2;i<max;i++){
            for (int j=i+1;j<max;j++){
                if (j%i==0) p[j] = true;
            }
        }

        for (int i = 2; i < p.length; i++) {
            int[] paper = new int[10];
            // 소수 일 때
            if (!p[i]) {
                String primeStr = String.valueOf(i);
                String[] split = primeStr.split("");
                for (int j = 0; j < split.length; j++) {
                    paper[Integer.parseInt(split[j])]++;
                }
                if (check(paper,l)) answer++;
            }
        }
        return answer;
    }
    
    // 종이 조각으로 만들 수 있는 수인가 판별
    public boolean check(int[] paper,List<String> l){
        // 종이 조각이랑 비교
        for (int k = 0; k < l.size(); k++) {
            paper[Integer.parseInt(l.get(k))]--;
        }

        for (int j = 0; j < paper.length; j++) {
            if (paper[j]>0)
                return false;
        }
        return true;
    }
}

 

[다른 사람 풀이 참고]

1. 종이 조각 모음으로 만들 수 있는 모든 경우의 수를 찾는다.

2. 1에서 찾은 수들 가운데 소수가 있는지 찾는다.

 

사실 문제를 처음 접했을 때 사실 위 방식의 해결법을 먼저 생각했으나, 1번 조건을 해결하지 못해서 [내풀이] 방식으로 푼것이었다..

 

1번 조건인 경우는 순열을 구하는 로직을 사용하면 해결할 수 있다.

 

문제는 순열을 구하는 로직을 이번에 알았다는 것이다. 다음에 쓸데가 많을 것 같다.

import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.Set;

class Solution {
    Set<Integer> set = new LinkedHashSet<>();
    
    public int solution(String numbers) {
        int answer = 0;
        int[] arr = new int[numbers.length()];
        int[] output = new int[numbers.length()];
        boolean[] visited = new boolean[numbers.length()];

        for (int i = 0; i < numbers.length(); i++) {
            arr[i] = Integer.parseInt(String.valueOf(numbers.charAt(i)));
        }

        for (int r = 1; r <= numbers.length(); r++) {
            perm(arr, output, visited, 0, numbers.length(), r);
        }

        Iterator<Integer> itr = set.iterator();
        while (itr.hasNext()){
            Integer next = itr.next();
            if (isPrime(next))
                answer++;
        }

        return answer;
    }
    
    void perm(int[] arr, int[] output, boolean[] visited, int depth, int n, int r) {
        if (depth == r) {
            StringBuilder s = new StringBuilder();
            for (int i = 0; i < r; i++) {
                s.append(output[i]);
            }
            set.add(Integer.parseInt(s.toString()));
            return;
        }

        for (int i = 0; i < n; i++) {
            if (visited[i] != true) {
                visited[i] = true;
                output[depth] = arr[i];
                perm(arr, output, visited, depth + 1, n, r);
                visited[i] = false;
            }
        }
    }

    boolean isPrime(int num) {
        if(num <= 1) return false;

        for(int i=2; i<=Math.sqrt(num); i++) {
            if(num % i == 0) return false;
        }
        return true;
    }
}

 

<문제 출처>

programmers.co.kr/learn/courses/30/lessons/42839