백준 3671번: 산업 스파이의 편지

import java.io.BufferedReader;

import java.io.File;

import java.io.FileReader;

import java.io.InputStreamReader;

import java.util.HashSet;

import java.util.StringTokenizer;

public class Main {

private static boolean Debug = true;

private static int PrimeCount;

static int[] pocket;

static HashSet<String> primeSet;

private static int NumberLen;

private static int T;

public static void main(String[] args) throws Exception {

BufferedReader br;

if (Debug) {

File f = new File("C:\\Users\\wvimi\\Downloads", "2048.txt");

FileReader reader = new FileReader(f);

br = new BufferedReader(reader);

} else {

br = new BufferedReader(new InputStreamReader(System.in)); // 직접입력시 이용

}

StringTokenizer st;

int TestLen = Integer.parseInt(br.readLine());

for (T = 0; T < TestLen; T++) {

String NumberStr = br.readLine();

NumberLen = NumberStr.length();

pocket = new int[NumberLen];

for (int i = 0; i < NumberLen; i++) {

pocket[i] = NumberStr.charAt(i) - '0';

}

// 탐색 리스트 초기화

primeSet = new HashSet();

findPath(0, "");

primeSet.remove("");

PrimeCount = 0;

for (String item : primeSet) {

// 소수라면 PrimeCount++

isPrime(Integer.parseInt(item));

}

// 소수의 개수 출력

System.out.println(PrimeCount);

}

}

// 소수 판별

private static boolean isPrime(int num) {

// 2 ~ 제곱근까지 검색

int end = (int) Math.sqrt(num);

for (int i = 2; i <= end; i++) {

if (num % i == 0) {

return false;

}

}

// 2보다 작으면 안되!

if (num < 2) {

return false;

}

PrimeCount++;

return true;

}

private static void findPath(int check, String input) {

// 중복되는 경우는 제거

if (primeSet.contains(input)) {

return;

} else {

primeSet.add(input);

}

// 0인 비트를 골라 1로 채운뒤, 문자열을 조립한다.

for (int i = 0; i < NumberLen; i++) {

int using = 1 << i;

// 시작은 0을 제외한다.

if (check == 0 && pocket[i] == 0) {

continue;

}

if ((check & using) == 0) {

findPath(check + using, input + pocket[i]);

}

}

}

public static void log(String input) {

if (Debug) {

System.out.println(input);

}

}

public static void log(String input, Object... args) {

if (Debug) {

System.out.println(String.format(input, args));

}

}

}