반응형
문제분석
조금 정직한 문제다.
1. numbers의 카드들이 존재하는데, numbers의 카드들을 재배열시켜서 만들수있는 숫자를 만든다.
2.만들어진 숫자들이 소수인지 확인한다.
3.소수의 갯수를 센다.
1. 순열 알고리즘으로 모든 숫자를 재배열시킨다.
->순열알고리즘은 구글링하면 나오지만, 돌아가는 로직은 알아두는게좋다.
->재배열한 숫자를 저장하는 리스트 하나 생성
1-2. 모든 경우의수를 정제한다.
EX) 00045, 001, 024 같은 숫자들은 45, 1,24 로 변환시켜야한다. String -> Integer 변환
EX) 소수는 2부터 시작하므로, 0,1인 숫자는 제거한다.
2.소수를 판별하는 알고리즘을 사용한다. (에라토네스의체)
->구글링하면 나온다.
3.소수 의갯수세기.
문제풀이
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
|
import java.util.*;
class Solution {
static List<String> cases = new LinkedList<>();
public int solution(String numbers) {
int answer = 0;
List<String> cards = new LinkedList<>();
List<String> result = new LinkedList<>();
String[] num_arr=numbers.split("");
for(String data: num_arr){
cards.add(data);
}
for(int i=1;i<=numbers.length();i++){
reculsion(cards,result,numbers.length(),i);
}
Set<Integer> case_dis =new HashSet<>();
for(String data:cases){
// 0과 1인경우는 제외하기위함. 2이상부터
if(Integer.valueOf(data)>1){
case_dis.add(Integer.valueOf(data));
}
}
for(int data:case_dis){
boolean flag =true;
if(data==2){
answer++;
continue;
}
for(int i=2;i<=Math.sqrt(data);i++){
if(data%i==0){
flag=false;
break;
}
flag=true;
}
if(flag==true){
answer++;
}
}
System.out.println(case_dis.toString());
return answer;
}
private static void reculsion(List<String> cards, List<String> result, int n, int r) {
if (r == 0) {
String temp="";
for(String data:result){
temp+=data;
}
cases.add(temp);
return;
}
for (int i = 0; i < n; i++) {
result.add(cards.remove(i));
reculsion(cards, result, n - 1, r - 1);
cards.add(i, result.remove(result.size() - 1));
}
}
}
|
cs |
반응형
'알고리즘 > 프로그래머스 Level2' 카테고리의 다른 글
[프로그래머스,Java] Level2: 게임 맵 최단거리 (1) | 2021.11.24 |
---|---|
[프로그래머스, Java] Level2:조이스틱 (0) | 2021.11.20 |
[프로그래머스,Java] Level2:가장 큰 수 (0) | 2021.11.13 |
[프로그래머스,Java] Level2: 프린터 (0) | 2021.11.10 |
[프로그래머스,자바] Level2: 전화번호 목록 (2021년 업데이트) (0) | 2021.11.08 |