[프로그래머스] 소수 찾기 Lv2, JavaScript

KUKJIN LEE • 4개월 전 작성

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

function solution(numbers) {
  let result = [];
  let nums = numbers.split("");
  function isPrime(num) {
    for (let i = 2; num > i; i++) {
      if (num % i === 0) {
        return false;
      }
    }
    return num > 1;
  }
  function getPermutation(arr, fixed) {
    if (arr.length >= 1) {
      for (let i = 0; i < arr.length; i++) {
        let newNum = fixed + arr[i];
        let copyArr = [...arr];
        copyArr.splice(i, 1);
        if (!result.includes(+newNum) && isPrime(+newNum)) {
          result.push(+newNum);
        }
        getPermutation(copyArr, newNum);
      }
    }
  }
  getPermutation(nums, "");
  return result.length;
}

isPrime 함수는 주어진 숫자가 소수인지 확인합니다.

2부터 해당 숫자 전까지 나누어 떨어지는지 확인합니다.
나누어 떨어지면 소수가 아니므로 false를 반환합니다.
1보다 큰 수 중 나누어 떨어지지 않으면 소수이므로 true를 반환합니다.

getPermutation 함수는 주어진 숫자들의 모든 순열을 생성합니다.

fixed는 현재까지 만들어진 숫자 문자열입니다.
각 재귀 호출에서 남은 숫자들 중 하나를 선택하여 fixed에 추가합니다.
새로 만들어진 숫자가 소수이고 아직 result에 없다면 추가합니다.
선택한 숫자를 제외한 나머지로 재귀 호출을 계속합니다.

getPermutation(nums, "");
return result.length;

초기 호출로 getPermutation을 빈 문자열과 함께 시작합니다.
최종적으로 찾은 소수의 개수(result 배열의 길이)를 반환합니다.

New Tech Posts

추천 도서

Our Channels

[프로그래머스] 소수 찾기 Lv2, JavaScript