[프로그래머스] 소수 찾기 (java) Math, 완전탐색
2020-03-10
소수 찾기 (프로그래머스> Math, 완전탐색)
문제설명
한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 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]를 만들 수 있습니다.
풀이
package Math;
public class prog_2_re_소수찾기 {
static int so[] = new int[9999999];
static int answer = 0;
static boolean sosu(int num) {
if(num==0 || num ==1) // 이거 까먹지 않도록
return false;
for(int i=2;i<=num-1; i++) {
if(num%i == 0)
return false;
}
return true;
}
static void swap(int arr[], int x, int y) {
int temp = arr[x];
arr[x] = arr[y];
arr[y] = temp;
}
static void perm(int arr[], int depth, int n, int r) {
if(depth == r) {
int num = 0;
for(int i=0; i<r; i++) {
num = num * 10 + arr[i];
}
if(so[num] == 0) {
so[num] = 1;
if(sosu(num))
answer++;
}
return;
}
for(int i=depth; i<arr.length; i++) {
swap(arr, i, depth);
perm(arr, depth+1, n, r);
swap(arr, i, depth);
}
}
static public int solution(String numbers) {
int arr[] = new int[numbers.length()];
for(int i=0;i<numbers.length(); i++)
arr[i] = numbers.charAt(i)-'0';
for(int i=1; i<=numbers.length(); i++) {
//arr,depth,n,r
perm(arr,0,numbers.length(),i);
}
return answer;
}
public static void main(String[] args) {
System.out.println(solution("17"));
}
}
후기 (20min)
이제 Permutation - 순열에 대해서는 코드짜는 법을 대강 익힌거 같다!
복습이라 금방 풀음, 또한 소수는 1과 2는 예외처리 필수!