[프로그래머스] 소수찾기 [Javascript]

 

https://school.programmers.co.kr/learn/courses/30/lessons/42839?language=javascript

문제 풀이 

 

해당 문제는 모든 조합 가능한 숫자를 만든 후 소수를 찾으면 되는 문제였다.

 

모든 조합 가능한 숫자를 만드는 방법은 순열을 이용해서 생성하면 된다.

 

순열 생성 코드

 

// 1) 특정 배열에 대한 "전체 길이" 순열 구하기
function permuteArray(arr) {
  // 원소가 1개 이하라면 그대로 반환
  if (arr.length <= 1) {
    return [arr];
  }

  const result = [];

  for (let i = 0; i < arr.length; i++) {
    // i번째를 고정(fixed)하여 재귀로 나머지 원소들의 순열을 구함
    const fixed = arr[i];
    const remaining = [...arr.slice(0, i), ...arr.slice(i + 1)];

    const perms = permuteArray(remaining);
    // 구한 순열에 fixed를 맨 앞에 붙여서 완성
    for (const perm of perms) {
      result.push([fixed, ...perm]);
    }
  }
  return result;
}

// 2) permuteArray를 이용해 문자열로 묶어서 반환
function getAllNumber(arr) {
  // 모든 순열(2차원 배열)을 구함
  const permutations = permuteArray(arr); // ex) [[1,7],[7,1]]
  // 순열을 문자열로 변환
  const result = permutations.map(perm => perm.join("")); 
  return result;
}

 

소수 판별하기

에라토스테네스의 체

https://blog.naver.com/falcon2026/221240012317

소수를 구하는 방법, 에라토스테네스의 체!

에라토스테네스의 체를 이용해서 소수인지 판별하는 함수를 작성한다.

 

최종 코드

 

function solution(numbers) {
  const arr = numbers.split("").map(Number);

  const allPerms = getAllPermutations(arr); 
  let candidates = allPerms.map(perm => parseInt(perm.join(""), 10));

  candidates = [...new Set(candidates)];

  candidates = candidates.filter(isPrime);

  return candidates.length;
}

function isPrime(num) {
  if (num < 2) return false;
  for (let i = 2; i * i <= num; i++) {
    if (num % i === 0) return false;
  }
  return true;
}


// arr에서 길이 r만큼 뽑은 순열을, 배열 형태로 반환
function permuteOfLength(arr, r) {
  // r이 1이면 각 원소 하나하나가 순열
  if (r === 1) {
    return arr.map(x => [x]);
  }

  const result = [];
  // 각 원소를 한 번씩 고정해 가면서
  for (let i = 0; i < arr.length; i++) {
    const fixed = arr[i];
    // 고정한 원소를 제외한 나머지
    const remaining = [...arr.slice(0, i), ...arr.slice(i + 1)];
    // 나머지에서 (r-1) 길이 순열을 구함
    const perms = permuteOfLength(remaining, r - 1);
    // 고정 원소(fixed)를 맨 앞에 붙임
    for (const perm of perms) {
      result.push([fixed, ...perm]);
    }
  }
  return result;
}

function getAllPermutations(arr) {
  let allPerms = [];

  // 길이 1부터 arr.length까지
  for (let r = 1; r <= arr.length; r++) {
    const perms = permuteOfLength(arr, r); 
    // 예: r=2면 길이 2짜리 순열을 모두 구함
    allPerms.push(...perms);
  }

  return allPerms; // 2차원 배열 형태
}