[Javascript] 소수 만들기 (12977)

문제링크

코딩테스트 연습 - 소수 만들기

접근방법

방법 1. nums 배열의 3개의 원소만 선택하는 조합을 구해서 구한 조합의 합을 배열로 만들기
방법 2. 완전 탐색을 통해 3중 for문으로 3개를 뽑는 모든 경우의 수를 구하기

방법 2는 3중 for문을 사용하기 때문에 O(n^3)이라 생각되어
먼저 방법 1을 선택하여 문제를 풀이하였다.

하지만 효율성에서 방법 2의 방식이 훨씬 더 빠른 속도를 보였다.

재귀함수와 배열 내장함수들의 시간복잡도에 대해 다시 학습해봐야겠다.

 

 

function solution(nums) {
    const sumArr = []
    const combinations = getCombinations(nums, 3)
    combinations.forEach(e => sumArr.push(e.reduce((a,b) => a+b)))
    let count = sumArr.length;
    
    sumArr.forEach(e => {
        for(let i = 2; i <= Math.sqrt(e); i++){
            if(e % i === 0){
                count--;
                break;
            }

        }
    })
    
    return count;
}

const getCombinations = function (arr, selectNumber) {
    const results = [];
    if (selectNumber === 1) return arr.map((el) => [el]); 

    arr.forEach((fixed, index, origin) => {
      const rest = origin.slice(index + 1); 
      const combinations = getCombinations(rest, selectNumber - 1);
      const attached = combinations.map((el) => [fixed, ...el]);
        
      results.push(...attached);
    });

    return results
}

function solution(nums) {
  let answer = 0;
  const length = nums.length;
  for (let i = 0; i < length; i++) {
    for (let j = i + 1; j < length; j++) {
      for (let k = j + 1; k < length; k++) {
        const sum = nums[i] + nums[j] + nums[k];
        if (isPrime(sum)) answer += 1;
      }
    }
  }

  return answer;
}

function isPrime(num) {
  for (let i = 2; i <= Math.sqrt(num); i++) {
    if (num % i === 0) return false;
  }
  return num >= 2;
}