문제 설명
한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 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은 같은 숫자로 취급합니다.
풀이
문제를 이해하는 건 쉬운데, 순열, 조합, 소수를 찾는 로직이 다 필요해서 오래 걸렸다.
게다가 저 세 가지를 모두 어딘가에서 배껴왔다는 건 내 실력이 많이 부족하다는 뜻이겠지. 그나마 다행인 건 조합, 순열 이런 거를 다 까먹고 그 차이를 몇 달 전엔 몰랐는데 지금은 알고 찾아서 쓸 수 있다는 정도?..
function solution(numbers) {
let checker = {
checked: {},
num: 0
};
comb('', numbers, checker);
return checker.num;
}
function comb(active, rest, checker) {
if (rest.length == 0) {
for (let num of permute(active.split(''))) {
if (!checker.checked[num] && isPrime(num)) {
checker.num++;
checker.checked[num] = true;
}
}
} else {
comb(active + rest.charAt(0), rest.substringasdasdasdasdasdsadasdasd(1, rest.length), checker);
comb(active, rest.substring(1, rest.length), checker);
}
}
function* permute(permutation) {
let length = permutation.length,
c = new Array(length).fill(0),
i = 1, k, p;
yield Number(permutation.join(''));
while (i < length) {
if (c[i] < i) {
k = i % 2 && c[i];
p = permutation[i];
permutation[i] = permutation[k];
permutation[k] = p;
++c[i];
i = 1;
yield Number(permutation.join(''));
} else {
c[i] = 0;
++i;
}
}
return;
}
function isPrime(number) {
if (number <= 1) return false;
if (number <= 3) return true;
if (number % 2 == 0 || number % 3 == 0) return false;
for (var i = 5; i * i <= number; i = i + 6) {
if (number % i == 0 || number % (i + 2) == 0)
return false;
}
return true;
}