[programmers] Lv2. 소수 찾기 Javascript | protect-me

protect-me·2021년 4월 29일

programmers 소수 찾기 javascript 소수찾기 javascript 소수찾기javascript 알고리즘 알고리즘문제풀이 프로그래머스

알고리즘 문제풀이 programmers Lv2

목록 보기

10/23

🕊 Link

Lv2. 소수 찾기 Javascript
https://programmers.co.kr/learn/courses/30/lessons/42839

🧑🏻‍💻 Code(javascript)

function primality(n) {
  if (n < 2) return false;
  let i = 2;
  while (i * i <= n) {
    if (n % i == 0) {
      return false;
    }
    i++;
  }
  return true;
}

function solution(numbers) {
  const arr = [...numbers];
  let result = [];
  const getNums = (fixed, arr) => {
    if (arr.length >= 1) {
      for (let i = 0; i < arr.length; i++) {
        const newFixed = fixed + arr[i];
        const restArr = arr.slice();
        restArr.splice(i, 1);
        result.push(newFixed);

        getNums(newFixed, restArr);
      }
    }
  };
  getNums("", arr);

  result = [...result].map((item) => Number(item));
  result = new Set(result);
  result = [...result].filter((item) => primality(Number(item)));
  return result.length;
}

💡 Solution

완전 탐색 문제로, 아래의 세 단계를 밟아 해결함.
1. 문자 뽑아내기
2. 소수 찾기
3. 기타 처리

1. 문자 뽑아내기

재귀함수를 활용한 순열

  let result = [];
  const getNums = (fixed, arr) => {
    if (arr.length >= 1) {
      for (let i = 0; i < arr.length; i++) {
        const newFixed = fixed + arr[i];
        const restArr = arr.slice();
        restArr.splice(i, 1);
        result.push(newFixed);

        getNums(newFixed, restArr);
      }
    }
  };
  getNums("", arr);

2. 소수 찾기

$[2, n]$ 의 범위에 약수가 존재하는지 확인하여 소수 판별 (시간복잡도: $O(√n)$ )

ex) $36$ 의 약수 = $[1, 2, 3, 4, 6, 9, 12, 18, 36]$
$36 = 1 * 36 = 2 * 18 = 3 * 12 = 4 * 9 = 6 * 6$

$36$ 의 약수는 $√36$ 이하의 값과 이상의 값의 짝으로 이루어져 있으므로,
$√36$ 이하의 값을 확인하면 이상의 값은 확인할 필요가 없음.
( $1$ 은 소수가 아니기 때문에 $i$ 는 $2$ 부터 시작)

function primality(n) {
  if (n < 2) return false;
  let i = 2;
  while (i * i <= n) {
    if (n % i == 0) {
      return false;
    }
    i++;
  }
  return true;
}

3. 기타 처리

숫자 변환, 중복 제거, 소수 찾기

  result = [...result].map((item) => Number(item)); // map : String to Number
  result = new Set(result); // set : 중복 제거
  result = [...result].filter((item) => primality(Number(item))); // filter : 소수 찾기
  return result.length; // 문제에서 원하는 값은 소수인 숫자의 갯수