(자바스크립트 알고리즘) 소수 찾기 Lv 2

코딩 기록/자바스크립트 알고리즘

(자바스크립트 알고리즘) 소수 찾기 Lv 2 - kimyang-sun

kimyang-Sun 2020. 11. 29. 20:08

문제 설명

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

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

제한 조건

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

입출력 예

문제 풀이

function solution(numbers) {
  let result = [];

  const filterPrime = num => {
    if (num < 2) return;
    for (let i = 2; i < num; i++) {
      if (num % i === 0) return;
    }
    result.push(num);
  }
  
  const getNumbersArr = (arr, num) => {
    if (num.length > 0) {
      filterPrime(+num);
    }
    if (arr.length > 0) {
      for (let i = 0; i < arr.length; i++) {
        const spliced = [...arr];
        spliced.splice(i, 1);
        getNumbersArr(spliced, arr[i] + num);
      }
    }
  }
  getNumbersArr(numbers, "");

  const answer = new Set(result);
  return answer.size;
}

풀이입니다.

우선 인자 numbers의 값을 순서대로 조합하여 모든 경우의 숫자의 조합으로 만들어줘야 하는데

이 경우는 순열, 조합에 쓰이는 재귀함수를 사용해주어야 합니다.

항상 재귀함수는 코드를 보면 조금 이해가 되지만 직접 사용해야하는 경우에는 어떤식으로 재귀를 해야하는지

떠오르지 않는 경우가 많아서 생각을 좀 잘해야 하나봅니다.. 😥

우선 filterPrime 함수를 만들어줬는데 이 함수는 인자로 받는 숫자가 소수인지 판별하여

소수라면 result 배열에 push 해주는 함수입니다.

이 부분은 어렵지 않습니다. 소수는 0과 1이 아닌 수 중에서 1과 자기자신으로만 나누어지는 수입니다.

그래서 들어오는 num 인자가 2보다 작으면 그냥 리턴해주고,

2부터는 for 반복문을 이용하여 num 미만까지 반복해주면서 i로 나뉘는 수가 있으면 리턴해줌으로써 걸러줍니다.

그리고 이 두패턴에 해당되지 않으면 소수이기에 result로 push 해주면 됩니다.

문제는 getNumbersArr 이라는 재귀함수인데 이 부분을 이해하기에 시간이 좀 걸렸습니다.. 😥

이 함수에는 인자로 두 개의 값이 들어갑니다. 처음 인자는 문자열 numbers를 넣어주고

두번째 인자로 들어가는 num에 초기값은 "" 빈 값을 넣어줍니다.

이 num 인자에는 재귀를 이용하여 앞으로 숫자들의 조합이 하나씩 들어올 예정입니다.

만약 들어오는 num이 존재한다면 filterPrime(+num)을 통해 소수를 걸러내주면 되는데 여기서 +를 해주는 이유는

만약 들어오는 조합된 수가 "011" 이라면 +를 곱해줌으로써 앞의 0을 없애주어야 하기 때문입니다.

그 뒤는 arr인자에 값이 존재한다면 for 반복문을 돌려주는데 arr.length 만큼 돌려줍니다.

여기에서는 들어오는 배열을 Spread 문법(전개구문)을 이용하여 새 배열을 만들어 spliced에 할당해줍니다.

그 이유는 전개구문을 활용하면 아예 새로운 arr이 복사되어 할당되고 그 값을 splice등으로 수정해주어도

기존의 arr값에는 변화가 없기 때문입니다.

그 후에 spliced를 splice(i, 1)을 이용하여 하나하나씩 잘라줍니다. 잘려서 남은 값은 getNumbersArr에 arr인자로

넣어주고 arr[i]는 잘린 숫자를 의미함으로 이 값에 num을 더해 조합하여 두번째 인자로 넣어줍니다.

이런식으로 계속해서 반복해서 getNumbersArr 함수가 실행되고,

그 함수는 계속해서 숫자를 result에 push 해주거나 또 하나하나씩 잘라서 getNumbersArr 함수를 실행시켜줍니다.

이 재귀함수는 arr 인자에 아무것도 존재하지 않을 경우 멈추는데, 그 경우는 splice(i, 1)이 하나하나씩 계속해서

잘라주기 때문에 결국에는 잘려서 남은 숫자가 하나도 없는경우가 생기는데 그 때 재귀가 멈추게 되는겁니다.

(전체를 다 하나하나씩 조합하고 끝남)

글로 길게 설명했지만 제가 쓰고도 잘 이해가 안되긴 하네요... 😑

이렇게 풀어서 result 배열이 만들어지고 그 값에는 모든 숫자의 조합들이 다 들어가있기 때문에

분명 반복되는 값들도 있을 수 있습니다. 그렇기에 new Set(result)를 이용하여 같은 숫자를 제거해줍니다.

이제 중복된 숫자가 제거된 answer의 length를 리턴해주면 되는데 그냥 answer.length를 리턴해주면

리턴이 되지 않습니다. 그 이유는 Set이라는 자료형 객체로 만들어주었기 때문에 더이상 배열이 아니기 때문입니다.

Set에는 기본적으로 객체의 수를 알려주는 size라는 키가 존재하기에 answer.size를 리턴해주면 됩니다.

또는 다시 Spread 문법을 이용하여 [...answer].length 를 리턴해주어도 값은 같습니다.

다른 사람들의 풀이

function solution(numbers) {
  const numberList = numbers.split('');
  const answers = findPrimeNumbers(numberList);

  return [...new Set(answers)].length;
}

function findPrimeNumbers(numberList, prevNumber) {
  const frontPaddingNumber = prevNumber || '';

  return numberList.reduce((primeNumbers, number, index) => {
    if (isPrimeNumber(Number(frontPaddingNumber + number))) {
      primeNumbers.push(Number(frontPaddingNumber + number));
    }

    const nextNumberList = [...numberList];
    nextNumberList.splice(index, 1);

    const result = findPrimeNumbers(
      nextNumberList,
      frontPaddingNumber + number,
    );
    primeNumbers.push(...result);

    return primeNumbers;
  }, []);
}

function isPrimeNumber(number) {
  const notPrime = [0, 1];
  if (notPrime.includes(number)) return false;

  for (let i = 2; i * i <= number; i++) {
    if (number % i === 0) return false;
  }

  return true;
}