문제 설명
한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.
제한사항
- numbers는 길이 1 이상 7 이하인 문자열입니다.
- numbers는 0~9까지 숫자만으로 이루어져 있습니다.
- "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.
입출력 예
| numbers | return |
| "17" | 3 |
| "011" | 2 |
풀이
수학.. 수학에서도 순열&조합을 알아야 수월하게 풀 수 있는 문제였던것 같다.
const getPermutations = (data,length) => {
const result = [];
if(length === 1) return data.map(el => [el]);
data.forEach((fixed, idx, origin) => {
const removeFixed = [...origin.slice(0, idx), ...origin.slice(idx+1)];
const permutation = getPermutations(removeFixed, length - 1).map(el => [fixed, ...el]);
result.push(...permutation);
})
return result;
}
const isPrimeNumber = (number) => {
if(number === 0) return 0;
let count = 0;
for(let i = 1; i <= number; i ++){
if(number % i === 0) count ++;
}
return count;
}
const solution = (numbers) => {
let result = [];
for(let i = 1; i <= numbers.length; i ++) result.push(...getPermutations([...numbers], i));
return result
.map(el => parseInt(el.join("")))
.filter((el, idx, arr) => arr.indexOf(el) === idx)
.map(el => isPrimeNumber(el))
.filter(el => el === 2).length;
}
getPermutations()는 재귀함수로, 주어진 갯수의 원소를 가진 모든 경우의 수를 리턴해주는 함수고,
isPrimeNumber()는 1부터 주어진 숫자까지의 모든 숫자중 해당 숫자의 약수의 갯수를 리턴해주는 함수다.
solution 함수에서는 number를 받아서, 1부터 number의 길이만큼 for문을 실행해준다.
getPermutations([...numbers], i)의 형태로
원소의 갯수가 1개인 모든 조합,
원소의 갯수가 2개인 모든 조합,
...
원소의 갯수가 i개인 모든 조합
위의 조합들을 result 배열에 넣어준다.
모든 조합의 경우의 수를 result에 담은 뒤,
우선 배열의 형태인걸 join() 매서드로 문자열로 변경 해준 뒤,
앞자리가 0으로 시작하는 것들을 제하기 위해서 parseInt()를 사용하였다.
그 뒤, filter()를 사용해 중복되는 원소들을 제거한 다음,
map()을 사용해서 각각의 원소에 isPrimeNumber()을 실행하여
각 원소의 약수의 갯수들로 이루어진 배열을 만들어 낸 뒤,
해당 배열에서 값이 2인 것들만을 filter()로 분류한다. (소수는 약수가 1과 자기자신 2개이므로)
그다음 해당 배열의 길이를 리턴해주면 끝.
문제 자체의 설명보다 순열을 구하는 재귀함수에 대한 설명이 더 중요한것 같아
추후에 다른 포스트에서 집중적으로 다뤄볼 예정.
