[프로그래머스_자바스크립트] Lv.1 소수 구하기 / 에라토스테네스의 체, 조합

 

[Javascript_ 소수 구하기]

 

프로그래머스

 

---

 

<STUDY>

 

📢 문제 📢

 

주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다.

숫자들이 들어있는 배열 nums가 매개변수로 주어질 때,

nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요.

 

제한사항

• nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다.
• nums의 각 원소는 1 이상 1,000 이하의 자연수이며, 중복된 숫자가 들어있지 않습니다.

 

❗ 아이디어

 

- 배열에서 3개를 뽑는 조합을 구하여 더한 값이 소수인지 확인한다.

 

---

 

<전체 코드>

 

// 소수 구하기
function isPrimeNumber(number) {
  if (number > 1) {
  // 에라토스테네스의 체
    for (let i = 2; i <= Math.sqrt(number); i++) {
      if (number % i === 0) return;
    }
    return true;
  }
}

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

  return answer;
}

 

---

 

<코드 설명>

 

☝ 소수 구하기

 

function isPrimeNumber(number) {
  if (number > 1) {
    for (let i = 2; i <= Math.sqrt(number); i++) {
      if (number % i === 0) return;
    }
    return true;
  }
}

 

- 에라토스테네스의 체를 이용하여 소수인 경우 true를 리턴한다. (소수를 구하는 방법 중 가장 빠름)

 

 

✌ 3개의 요소의 합이 소수인지 확인하기

 

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

  return answer;
}

 

- 맨 처음 고정 요소를 설정한 뒤 차례로 조합하여 요소끼리의 합이 소수이면 answer을 증가시킨다.

 

 

---

 

❗ 조합 배열 이용하기

 

처음에는 아래 코드처럼 조합 배열을 구하는 함수를 만들어 사용했다

정답은 맞았지만 시간 효율이 좋지 않아 위 방법으로 다시 바꾸었다.

 

function isPrimeNumber(number) {
  if (number > 1) {
    for (let i = 2; i <= Math.sqrt(number); i++) {
      if (number % i === 0) return;
    }
    return true;
  }
}

// 조합 배열 구하기
function getCombination(arr, num) {
  if (num === 1) return arr;

  let result = [];
  arr.forEach((ele, index, array) => {
    const rest = array.slice(index + 1);
    const combinations = getCombination(rest, num - 1);
    const attached = combinations.map(value => {
      return [ele, ...[].concat(value)];
    });
    result.push(...attached)
  });

  return result;
}

function solution(nums) {
  let answer = 0;
  const arr = getCombination(nums, 3);

  arr.map(item => {
    const sum = item.reduce((sum, value) => sum + value, 0);
    if (isPrimeNumber(sum)) answer++;
  })

  return answer;
}

 

- getCombination()을 이용하여 조합 배열을 구하고 map과 reduce를 이용하여 각 요소들의 합이 소수인지 확인한다.

 

---

 

🔆프로그래머스 Lv.1 소수 구하기🔆

 

👉ez1n github 구경하기👈

 

ez1n - Overview