문제 설명
한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.
제한사항
- numbers는 길이 1 이상 7 이하인 문자열입니다.
- numbers는 0~9까지 숫자만으로 이루어져 있습니다.
- "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.
입출력 예
| numbers | return |
|---|---|
| "17" | 3 |
| "011" | 2 |
나의 풀이
function solution(numbers) {
let number = [...numbers];
let answer = [];
for(let i = 1; i <= number.length; i++){
permutation(number, i).forEach(v =>sosu(+v) ? answer.push(+v) : v);
}
return new Set(answer).size;
}
// 소수 판별
function sosu(number) {
if(number === 1 || number === 0) return false;
for(let i = 2; i < number; i++) {
if(!(number % i)) return false;
}
return true;
}
// 순열 경우의 수 찾기
function permutation(arr, num) {
let result = [];
if(num === 1) return arr;
arr.forEach((v,i,origin) => {
let restArr = origin.filter((value,index) => index !== i);
let permuArr = permutation(restArr, num - 1);
let arr = permuArr.map(val => v + val);
result.push(...arr)
})
return result;
}우선 문자열이 조합될 수 있는 모든 경우의 수를 구해야한다.
순열을 이용하여 모든 경우의 수를 구하기 위해 permutation(arr, num) 함수를 만들었다.
arr, num은 arr배열 중에서 num개를 택하여 배열로 반환해준다.
예를 들어 [1,2,3,4] 중 2개를 택할 경우
- 1을 선택하고 나머지 [2,3,4] 중에 2개씩 조합한다. => [1,2,3], [1,2,4], [1,3,4]
- 2를 선택하고 나머지 [3,4] 중에 2개씩 조합한다. => [2,3,4]
- 3을 선택하고 나머지 [4] 중에 2개씩 조합한다. => []
- 4를 선택하고 나머지 [] 중에 2개씩 조합한다. => []
이런식으로 동작하게 된다.
따라서 forEach문으로 처음부터 끝까지 한번씩 숫자를 고정시키고 filter()를 이용하여 현재 인덱스와 같지 않은 숫자들을 restArr로 저장한다.
고정되지 않은 숫자들은 재귀 함수로 돌려주고 선택하는 숫자가 1이 되면 배열을 반환한다.
그리고 반환된 값들과 고정한 값을 합쳐주고 중첩된 배열을 스프레드 연산자를 이용하여 1차원 배열로 만들어준 후 result에 넣어준다.
그렇게 나온 경우의 수들을 sosu() 함수를 이용해 소수 판별을 해준다.
소수는 1과 자기 자신밖에 없기 때문에 중간에 하나라도 나머지가 0이 되는 수가 있다면 소수로 판단했다.
따라서 우선 1과 0일 경우 false를 리턴한다. 그리고 2부터 number 전까지 for문을 돌리면서 만약 나머지가 0이 되는 수가 있다면 false를 리턴했다
그래서 소수일 경우 answer에 넣어 주고 Set()을 사용하여 중복을 제거 한 후 나온 Set().size를 리턴해주었다.
