📂문제 설명
한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.
제한사항
- numbers는 길이 1 이상 7 이하인 문자열입니다.
- numbers는 0~9까지 숫자만으로 이루어져 있습니다.
- 013은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.
입출력 예
numbersreturn
17 | 3 |
011 | 2 |
입출력 예 설명
예제 #1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.
예제 #2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.
- 11과 011은 같은 숫자로 취급합니다.
📂아이디어 및 알고리즘(문제 풀이)
- 먼저 조합으로 풀지 혹은 순열로 풀지 고민해야 한다. 나는 여기서 조합을 먼저 생각했지만 너무 복잡해질거 같아서 순열을 이용하여 풀도록 하였다.
- String numbers를 char[]배열로 바꿔주어서 넣어주어 순회를 하기 쉽게 만들었다. 이 문제는 순열과 소수 찾기를 필요로 하기 때문에
- 순열을 만드는 perm 함수와 소수를 찾는 PrimeNum 함수를 만들었다.
- 순열 함수 Perm( char[] arr , int depth, int k, Set sosu )
- depth와 k를 이용하여 현재 몇개의 수를 뽑아 냈는지를 계속 확인해준다.
- 재귀함수로 매번 순회하면서 i, depth의 arr[index]값을 계속해서 바꿔준다. [ 순열 순서를 매번 바꿔준다. ]
- 1번째 swap에서는 순열을 바꿔줌으로서 depth를 순회하고
- 2번째 swap에서는 바뀌었던 순열들을 다시 원래대로 돌리는 과정이다.
- depth == k 가 되는 순간 make_num()을 통해 char[]을 String으로 만들어준다.
- [ 맨 밑에 순열 로직에 대한 링크를 달아두었다 ]
- 소수 PrimeNum(int n)
- n을 기준으로 2부터 n까지의 소수를 찾아내는 함수이다.
- 여기서 사용한 방법은 "에라토스테네스의 체"로 소수를 판별했다.
- Boolean PrimeArr[] 로 소수가 아닌 수는 true로 하여 구분하였고
- Judge_Prime()함수에서 해당 수에 값이 false이면 소수이므로 HashSet에 저장하도록 하였다.
📂소스 코드
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
|
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Set;
class Solution {
static boolean[] PrimeArr = new boolean[10000000];
public int solution(String numbers) {
char[] numbers_char = numbers.toCharArray();
PrimeNum(10000000);
//소수 구하기 (중복제외)
Set<Integer> sosulist = new HashSet<Integer>();
//i는 수열의 자릿수를 의미한다.
for(int i=1;i<=numbers_char.length;i++) {
perm(numbers_char,0,i,sosulist);
}
return sosulist.size();
}
// depth는 현재 몇개 뽑아냈는지, k는 몇개를 뽑아내서 순열을 만들것인지
public static void perm(char[] arr, int depth, int k, Set sosu) {
if(depth == k) {
make_num(arr,k,sosu);
return;
}
for(int i=depth;i<arr.length;i++) {
swap(arr, i, depth);
perm(arr, depth+1, k, sosu);
swap(arr, i, depth);
}
}
//char배열을 String으로
public static void make_num(char[] arr, int k, Set sosu) {
StringBuilder str = new StringBuilder();
for(int i=0;i<k;i++) {
str.append(arr[i]);
}
JudgePrime(sosu, str);
}
//소수 찾기
public static void PrimeNum(int n) {
//소수가 아니면 전부 true
PrimeArr[0] = PrimeArr[1] = true;
for(int i= 2; i*i<n ;i++) {
if(!PrimeArr[i]) {
for(int j = i*i;j<n;j +=i) PrimeArr[j] = true;
}
}
}
//소수 판단
public static void JudgePrime(Set sosu, StringBuilder str) {
int num = Integer.parseInt(String.valueOf(str));
if(!PrimeArr[num]) sosu.add(num);
}
public static void swap(char[] arr, int x, int y) {
char temp = arr[x];
arr[x] = arr[y];
arr[y] = temp;
}
}
|
cs |
📂코드 결과
📂후일담
간단한 문제인줄 알았는데 나에게 너무 힘든 시련을 주었던 문제이다.💨 조합으로 풀려 했던 난 많은 시간을 버리고 난 후에야 순열로 해야하나? 싶었고 처음에 바로 로직이 생각나지 않아서 고뇌한 시간이 많았다. 그러다 밑에 하단에 링크를 통해 다시 공부했고 풀 수 있었다. [ 노력하도록 하자... ]
이번 기회에 순열에 관한 트리를 다시 공부 할 수 있어서 좋았다🔥🔥🔥
[ JAVA_순열 로직 링크 ] https://gorakgarak.tistory.com/522
'알고리즘(Java) > programmers' 카테고리의 다른 글
[JAVA] 체육복 (코딩테스트 고득점 Kit [ Greedy(탐욕법) ]) - LEVEL1 (0) | 2020.09.02 |
---|---|
[JAVA] 카펫 (코딩테스트 고득점 Kit [ 완전탐색 ]) - LEVEL2 (0) | 2020.08.31 |
[JAVA] 모의고사 (코딩테스트 고득점 Kit [ 완전탐색 ]) - LEVEL1 (0) | 2020.08.30 |
[JAVA] H - Index(코딩테스트 고득점 Kit [ 정렬 ]) - LEVEL2 (0) | 2020.08.30 |
[JAVA]가장 큰 수(코딩테스트 고득점 Kit [ 정렬 ]) - LEVEL2 (0) | 2020.08.26 |