문제 설명
한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 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은 같은 숫자로 취급합니다.
======================================================================================================
import java.util.*;
class Solution {
public int solution(String numbers) {
int answer = 0;
String tempNumbers[] = numbers.split(“”);
List
//소수배열
boolean [] decimal = getDecimal(numbers);
//입력된 숫자로 만든 모든 수
returnArr = result(arr,returnArr,"");
//숫자로 변환
//changeStringToInt(returnArr);
HashSet<Integer> intHashSet = changeStringToInt(returnArr);
Iterator iter = intHashSet.iterator();
while(iter.hasNext()) {
int a = (int)iter.next();
if(!decimal[a]){
answer++;
}
}
return answer;
}
public boolean[] getDecimal(String numbers){
//만들수 있는 제일 큰 숫자까지 배열을 선언
String tempb[] = numbers.split("");
Arrays.sort(tempb);
String tempMax="";
for(int i=tempb.length-1;i>=0;i--){
tempMax +=tempb[i];
}
int max = Integer.parseInt(tempMax);
boolean prime[] = new boolean[max+1];
// 구하고자 하는 숫자 범위
int N = max;
// 소수는 false
// 1은 소수가 아니므로 제외
prime[0] = prime[1] = true;
for(int i=2; i*i<=N; i++){
// prime[i]가 소수라면
if(!prime[i]){
// prime[j] 소수가 아닌 표시
for(int j=i*i; j<=N; j+=i) {
prime[j] = true;
}
}
}
return prime;
}
//입력된 숫자로 만들수 있는 모든 숫자를 구함
public ArrayList<String> result(List<String> arr, ArrayList<String> returnArr, String temp){
String loopTemp=temp;
for(int i=0;i<arr.size();i++) {
loopTemp += arr.get(i);
returnArr.add(loopTemp);
if(arr.size()!=1){
ArrayList<String> tempArr = new ArrayList<>(arr);
tempArr.remove(i);
result(tempArr,returnArr,loopTemp);
}
loopTemp = temp;
}
return returnArr;
}
//입력된 숫자중 0을 제거하여 중복 제거
public HashSet<Integer> changeStringToInt(ArrayList<String> stringList){
HashSet<Integer> intHashSet = new HashSet<Integer>();
for(int i=0;i<stringList.size();i++){
intHashSet.add( Integer.parseInt(stringList.get(i)));
}
return intHashSet;
} }
=================================================================================================================
import java.util.*;
class Solution {
public int solution(String numbers) {
int answer = 0;
boolean [] decimal = getDecimal(numbers);
String tempNumbers[] = numbers.split(“”);
List
return answer;
}
public boolean[] getDecimal(String numbers){
//만들수 있는 제일 큰 숫자까지 배열을 선언
String tempb[] = numbers.split("");
Arrays.sort(tempb);
String tempMax="";
for(int i=tempb.length-1;i>=0;i--){
tempMax +=tempb[i];
}
int max = Integer.parseInt(tempMax);
boolean prime[] = new boolean[max+1];
// 구하고자 하는 숫자 범위
int N = max;
// 소수는 false
// 1은 소수가 아니므로 제외
prime[0] = prime[1] = true;
for(int i=2; i*i<=N; i++){
// prime[i]가 소수라면
if(!prime[i]){
// prime[j] 소수가 아닌 표시
for(int j=i*i; j<=N; j+=i) {
prime[j] = true;
}
}
}
return prime;
}
//입력된 숫자로 만들수 있는 모든 숫자를 구함
public ArrayList<String> result(List<String> arr, ArrayList<String> returnArr, String temp){
String loopTemp=temp;
for(int i=0;i<arr.size();i++) {
loopTemp += arr.get(i);
returnArr.add(loopTemp);
if(arr.size()!=1){
ArrayList<String> tempArr = new ArrayList<>(arr);
tempArr.remove(i);
result(tempArr,returnArr,loopTemp);
}
loopTemp = temp;
}
return returnArr;
} }