문제 설명
한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 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 {
Set<Integer> primeSet;
String numbers;
public int solution(String numbers) {
boolean[] isUsed = new boolean[numbers.length()];
primeSet = new HashSet<>();
this.numbers = numbers;
StringBuilder sb = new StringBuilder();
search(sb, isUsed);
return primeSet.size();
}
void search(StringBuilder sb, boolean[] isUsed) {
if (sb.length() >= numbers.length()) {
return;
}
for (int i = 0; i < numbers.length(); i++) {
if (isUsed[i]) {
continue;
}
char ch = numbers.charAt(i);
sb.append(ch);
int num = Integer.parseInt(sb.toString());
if (isPrime(num)) {
primeSet.add(num);
}
StringBuilder _sb = new StringBuilder(sb);
isUsed[i] = true;
search(_sb, isUsed.clone());
sb.deleteCharAt(sb.length() - 1);
isUsed[i] = false;
}
}
boolean isPrime(int n) {
if (n == 1 || n == 0) return false;
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
}
Java
복사
Remark
•
풀이 아이디어
◦
isPrime 메서드로 소수 판정
◦
재귀함수로 완전탐색
▪
StringBuilder에 종이조각을 하나 넣음
▪
StringBuilder의 문자열을 꺼내 숫자로 만들고, 소수판정 후 소수이면 set에 넣음
▪
종이조각을 사용했다는 사실을 boolean 배열에 체크하고 재귀함수 호출하며 StringBuilder와 boolean 배열을 복사해서 넘김
▪
넘긴 이후 StringBuilder에 넣었던 종이조각을 도로 꺼내고 boolean 배열에 체크한 것을 원상복구
▪
for문에 의해 다음 종이조각을 넣는 경우의 수로 이동
•
다른 분들 풀이
import java.util.HashSet;
class Solution {
public int solution(String numbers) {
HashSet<Integer> set = new HashSet<>();
permutation("", numbers, set);
int count = 0;
while(set.iterator().hasNext()){
int a = set.iterator().next();
set.remove(a);
if(a==2) count++;
if(a%2!=0 && isPrime(a)){
count++;
}
}
return count;
}
public boolean isPrime(int n){
if(n==0 || n==1) return false;
for(int i=3; i<=(int)Math.sqrt(n); i+=2){
if(n%i==0) return false;
}
return true;
}
public void permutation(String prefix, String str, HashSet<Integer> set) {
int n = str.length();
//if (n == 0) System.out.println(prefix);
if(!prefix.equals("")) set.add(Integer.valueOf(prefix));
for (int i = 0; i < n; i++)
permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n), set);
}
}
Java
복사
◦
StringBuilder 대신 그냥 String 형태로 넘김
◦
나처럼 boolean 배열을 쓰는 게 아니라 substring을 통해 사용된 문자를 제외하고 넘김
◦
속도는 10배 정도 느리지만 코드가 간결함