[Programmers] 소수 찾기

JaeungE·2021년 7월 6일

PS with Java

PS

목록 보기

17/22

문제 출처 : [Programmers] 소수 찾기, https://programmers.co.kr/learn/courses/30/lessons/42839

👨‍🏫문제

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

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

💻코드

import java.util.ArrayList;

class Solution {
    public int solution(String numbers) {
        int answer = 0;
        char[] c = numbers.toCharArray();
        boolean[] visited = new boolean[10];
        StringBuilder sb = new StringBuilder();
        ArrayList<Integer> list = new ArrayList<>();
        
        // 한 자리 수부터 문자열 길이에 해당하는 자리수까지 모든 순열을 구한다.
        for(int i = 1; i <= c.length; i++){
            permutation(c, sb, visited, list, 0, i);
        }
        
        // list에서 순서대로 값을 뽑고, 소수인 경우 answer 변수를 증가시킨다.
        for(int i = 0; i < list.size(); i++){
            if(isPrime(list.get(i))){
                answer++;
            }
        }
        
        return answer;
    }
    
    // 입력 문자열로부터 순열을 만들어주는 함수
    static public void permutation(char[] c, StringBuilder sb, boolean[] visited, ArrayList<Integer> list, int depth, int target){
        if(depth == target){
            int num = Integer.parseInt(sb.toString());
		
       	    // list에 해당 값이 존재하지 않는 경우에만 추가한다.
            if(!list.contains(num)){
                list.add(num);
                return;
            }
        }

        for(int i = 0; i < c.length; i++){
            if(!visited[i]){
                visited[i] = true;
                sb.append(c[i] + "");
                permutation(c, sb, visited, list, depth + 1, target);
                visited[i] = false;
                sb.delete(sb.length() - 1, sb.length());
            }
        }
    }
    
    // 매개 변수로 들어온 정수가 소수인지 판별해주는 함수
    static boolean isPrime(int num){
        if(num >= 0 && num <= 1){
            return false;
        }

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

        return true;
    }
}