소수 만들기

소수 만들기

function isPrimeNumber(num) {
  if (num < 2) {
    return false;
  }
  if (num < 4) {
    return true;
  }
  if (num % 2 == 0 || num % 3 == 0) {
    return false;
  }
  for (let i = 5; i * i <= num; i += 6) {
    if (num % i == 0 || num % (i + 2) == 0) {
      return false;
    }
  }
  return true;
}

function solution(nums) {
  let count = 0;
  function combination(pre, arr) {
    if (pre.length == 3) {
      const sum = pre.reduce((acc, cur) => {
        acc += cur;
        return acc;
      }, 0);
      if (isPrimeNumber(sum)) {
        count++;
      }
      return;
    }
    for (let i = 0; i < arr.length; i++) {
      const copiedPre = pre.slice();
      copiedPre.push(arr[i]);
      combination(copiedPre, arr.slice(i + 1));
    }
  }
  combination([], nums);
  return count;
}

• 여태껏 조합 만드는 건 JS100제에서 배웠던 방식으로 했었는데 재귀를 안 쓰고도 조합을 만드는 훨씬 깔끔하고 성능도 좋은 방식이 있었다

function isPrimeNumber(num) {
  if (num < 2) {
    return false;
  }
  if (num < 4) {
    return true;
  }
  if (num % 2 == 0 || num % 3 == 0) {
    return false;
  }
  for (let i = 5; i * i <= num; i += 6) {
    if (num % i == 0 || num % (i + 2) == 0) {
      return false;
    }
  }
  return true;
}

function solution(nums) {
  let count = 0;
  const length = nums.length;
  for (let i = 0; i < length - 2; i++) {
    for (let j = i + 1; j < length - 1; j++) {
      for (let k = j + 1; k < length; k++) {
        if (isPrimeNumber(nums[i] + nums[j] + nums[k])) {
          count++;
        }
      }
    }
  }
  return count;
}

• 그런데 생각해보니 조합의 원소 개수가 많으면 많을수록 중첩 반복문을 여러번 작성해야 되기 때문에 상황에 맞춰서 쓰면 될 것 같다.

• 효율성 면에서 엄청 차이를 보이는 것도 아니니까...