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

문제 설명

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

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

제한사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

문제 풀이

이 문제를 풀기 위해선

1. 완전 탐색(순열)과
2. 소수 판별 방법

에 대해 이해해야 합니다.

순열

순열에 대한 기본적인 설명은 이 링크에서 확인할 수 있습니다.

가능한 모든 숫자 조합을 완전 탐색하기 위해 순열 알고리즘을 사용했습니다. 이 때, 순열을 시작하게 될 값과 숫자 조합의 자릿수도 완전탐색에 반영하기 위해 각각 반복문을 지정해줬습니다.

순열을 이용한 완전 탐색의 코드는 아래와 같습니다.

let nums = [];

  // 조합 가능한 숫자를 찾는 로직
  const permutation = (output, rests, length) => {
    if (output.length === length) {
      if (!nums.includes(output * 1)) nums.push(output * 1);
      return;
    }
    rests.forEach((v, i) => {
      const nextOutput = `${output}${v}`;
      const nextRests = rests.filter((_, restIdx) => restIdx !== i);
      permutation(nextOutput, nextRests, length);
    });
  };

  // arr의 모든 값들을 시작값으로 지정하기 위해 반복문 수행
  for (let i = 0; i < arr.length; i++) {
    const firstSelect = arr[i];
    const firstRests = arr.filter((_, restIdx) => restIdx !== i);

    // 1부터 최대 자릿수까지 순회
    for (let j = 1; j <= arr.length; j++) {
      permutation(firstSelect, firstRests, j);
    }
  }

소수 찾기

가능한 모든 숫자들의 조합들을 찾아주었다면, 이제 해당 숫자들이 소수인지 판별해줘야 합니다. 소수 판별 방식에는 여러가지 방법들이 있지만, 저는 Math.sqrt(숫자)까지 순회하며 소수인지 판별하는 로직을 이용했습니다.

소수인지 아닌지 판별하는 코드는 아래와 같습니다.

// 소수 판별 핸들러
const checkPrimeNumber = (number) => {
  if (number < 2) return false;

  for (let i = 2; i <= Math.sqrt(number); i++) {
    const remainder = number % i;
    if (remainder === 0) return false;
  }
  return true;
};

// 소수만 남기고 제거
nums = nums.filter((v) => checkPrimeNumber(v * 1));

마지막으로 남은 소수들의 수를 구하여 리턴해주면 코드는 완성입니다.

전체 코드

const solution = (numbers) => {
  const arr = numbers.split("");
  let nums = [];

  // 조합 가능한 숫자를 찾는 로직
  const permutation = (output, rests, length) => {
    if (output.length === length) {
      if (!nums.includes(output * 1)) nums.push(output * 1);
      return;
    }
    rests.forEach((v, i) => {
      const nextOutput = `${output}${v}`;
      const nextRests = rests.filter((_, restIdx) => restIdx !== i);
      permutation(nextOutput, nextRests, length);
    });
  };

  // arr의 모든 값들을 시작값으로 지정하기 위해 반복문 수행
  for (let i = 0; i < arr.length; i++) {
    const firstSelect = arr[i];
    const firstRests = arr.filter((_, restIdx) => restIdx !== i);

    // 1부터 최대 자릿수까지 순회
    for (let j = 1; j <= arr.length; j++) {
      permutation(firstSelect, firstRests, j);
    }
  }

  // 소수 판별 핸들러
  const checkPrimeNumber = (number) => {
    if (number < 2) return false;

    for (let i = 2; i <= Math.sqrt(number); i++) {
      const remainder = number % i;
      if (remainder === 0) return false;
    }
    return true;
  };

  nums = nums.filter((v) => checkPrimeNumber(v * 1));
  return nums.length;
};

마무리하며

덕분에 수열에 대해 배우고 이를 응용하는 연습을 할 수 있었던 좋은 문제인 것 같습니다.