[Java] 백준 3671번 : 산업 스파이의 편지*

1. 문제

https://www.acmicpc.net/problem/3671

3671번: 산업 스파이의 편지

 

 

2. 풀이 과정

1. 주어지는 input의 숫자 하나하나를 int[]로 변환한다.

2. 순열을 이용하여 모든 경우의 수를 탐색한다.

3. 집합으로 중복된 값은 소수 판단 여부에서 제외한다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;

public class Main {
    static Set<Integer> set;
    static int result, len, input[];

    public static void permutation(int order, int num, int visited){
        if(!set.contains(num)){
            set.add(num);
            if(isPrime(num)){result++;}
        }

        //permutation
        for(int i=0; i<len; i++){
            if((visited & (1<<i))!=0){continue;}
            permutation(order*10, num+input[i]*order, visited | (1<<i));
        }

    }

    public static boolean isPrime(int su){
        int limit = (int)Math.sqrt(su);
        if(su <= 1){
            return false;
        }
        for(int i=2; i<=limit; i++){
            if(su%i==0){return false;}
        }
        return true;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());
        while(T-- > 0){
            String inputs = br.readLine();
            len = inputs.length();
            set = new HashSet<>();
            result = 0;
            input = new int[len];
            for(int i=0; i<len; i++){
                input[i] = inputs.charAt(i) -'0';
            }

            permutation(1, 0, 0);
            sb.append(result+"\n");
        }
        System.out.println(sb.toString());

    }

}

 

결과