코드 풀이
// 조합으로 배열의 모든 경우의 수 구하기(시간복잡도는 O(2^N))
const getCombinations = (arr, n) => {
const results = [];
// n이 1이 되는 경우는 현재값을 선택하는 것과 동일
// 따라서 각각의 원소를 바로 배열 형태로 리턴
// 재귀호출에서 n이 1이 되는 순간부터 배열 데이터 생성
// 즉 1부터 역으로 다시 거슬러 올라가 n이 될때까지
// 선택된 원소들로 배열(조합)을 구성
if (n === 1) return arr.map((el) => [el]);
// 처리할 현재 요소, 현재 요소의 인덱스, 배열
arr.forEach((fixed, index, origin) => {
// 처리할 현재 요소를 제외한 배열
const rest = origin.slice(index + 1);
// 만약 제외한 배열의 길이가 selectNumber-1보다 작다면 반복문 취소
if(rest.length < n-1) return false;
// 제외한 배열의 조합 구하기 (재귀)
const combinations = getCombinations(rest, n - 1);
// 현재요소와 조합으로 구한 배열 합쳐서 배열로 리턴
const attached = combinations.map((el) => [fixed, ...el]);
// result에 각 요소를 담아준다
results.push(...attached);
});
return results; // 결과 담긴 results return
}
// 조합의 각 요소들의 합을 구해서 배열로 리턴(시간복잡도: O(N))
const getSums = (arr) => {
// 이중 배열이기때문에 해당 배열의 요소의 배열합을 map, reduce 함수를 사용하여 구함
const sums = arr.map(el => {
const sum = el.reduce((acc, cur) => acc+cur)
return sum;
})
return sums;
}
// 소수판별하기(시간복잡도는 O(√N))
const isPrime = (n) => {
for (let i = 2; i <= Math.sqrt(n); i++) {
if (n % i === 0) return false;
}
return true;
}
// 결과적으로 시간복잡도는 O(2^N)
function solution(nums) {
// 배열에서 중복되지 않는 3개의 수의 조합을 구하고
// 그 조합의 배열인 요소의 합을 요소로 가진 배열 구하기
let combination = getSums(getCombinations(nums,3));
// 그 배열의 요소가 소수인 개수 구하기
let answer = combination.reduce((acc, cur) => acc + isPrime(cur),0)
return answer;
}