[프로그래머스] 완전탐색 - 소수 찾기 (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은 같은 숫자로 취급합니다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60

static boolean[] prime; static int count = 0;   public static void prime(int n) {   int tmp = (int)Math.pow(10, n);   prime = new boolean[tmp + 1];   prime[0] = prime[1] = true;   for (int i = 2; i * i < tmp; i++) {       if (prime[i])           continue;   for (int j = i * i; j < tmp; j += i)       prime[j] = true;   } }   public static void permutation(int[] arr, int depth, int n, int r) {     if (depth == r) {       if (check(arr, r))       count++;   }     for (int i = depth; i < n; i++) {     swap(arr, depth, i);     permutation(arr, depth + 1, n, r);     swap(arr, depth, i);   } }   public static void swap(int[] arr, int depth, int i) {   int temp = arr[depth];   arr[depth] = arr[i];   arr[i] = temp; }   // 배열 출력 public static boolean check(int[] arr, int r) {   StringBuilder sb = new StringBuilder();   for (int i = 0; i < r; i++)       sb.append(arr[i] + "");   int tmp = Integer.parseInt(sb.toString());   if (!prime[tmp]) {     prime[tmp] = true;     return true;   }   return false; }     public int solution(String numbers) {   int len = numbers.length();   int[] num = new int[len];   for (int i = 0; i < len; i++)   num[i] = Integer.parseInt(String.valueOf(numbers.charAt(i)));   prime(numbers.length());   for(int i = 1; i <= len; i++)   permutation(num, 0, len, i);     return count; } Colored by Color Scripter

cs

순열과 에라토스테네스의 체를 이용해서 문제를 풀었다.

우선 주어진 수의 길이가 k 라고 하면 10^k + 1의 boolean 배열 prime을 만든다. 이 배열을 이용해서 소수이면 false, 아니면 true로 만들어준다.

그리고 순열을 이용해서 만들 수 있는 수들을 소수인지 아닌지 prime배열로 체크해서 문제를 해결한다.

순열 알고리즘은 여기를 참고해서 코드를 작성하였다.