완전 탐색 문제마다 매일 막히는 것 같아서 완전 탐색 문제들에 좀 더 익숙해지기 위해서 완전 탐색 카테고리를 풀어봤다. Level 2인데도 불구하고 생각해내는 데 오래 걸려서 좀 많이 슬펐다..

이 문제에서는 수를 조합해서, 그 숫자가 소수인지를 판별해야한다. 그러기 위해서 필요한 것을 정리해봤다.

  • 한 자리 숫자를 조합해 여러 자리 숫자를 만드는 기능
  • 만들어진 숫자가 소수인지 판별하는 기능

소수 판별은 꽤나 자주 만날 수 있는 문제이기 때문에, 어렵지 않게 만들어낼 수 있다. 하지만 한 자리 숫자를 조합해서 여러 자리 숫자를 어떻게 만들어야할지 좀처럼 잘 방법이 떠오르지 않았다.

풀이

여러 개의 숫자를 조합하고 소수 판별을 하기 위해서 일단 for문을 통해서 어떻게 만들어낼 수 있을지 생각해봤다.

예를 들어 [1, 7]이 주어졌다면 아래와 같이 동작하면서 답을 찾아야 할 것이다.

  1. 1이 소수인지 판별
  2. 17을 만들어서 소수인지 판별
  3. 7이 소수인지 판별
  4. 71이 소수인지 판별

그런데 문제는 총 몇자리가 주어질지 모르기 때문에, 중첩 포문으로 만들기엔 무리가 있을 것 같아서 일단 for문으로 위 상황에 대해 만들어 본 다음에 재귀로 바꿔보았다. (아직도 재귀는 바로 생각해내기 너무 어렵다..😥)

그래서 구현한 재귀 함수는 findPrimeNumbers()인데, 자신에 대한 소수 판별을 한 뒤 자기 자신을 제외한 배열과, 앞자리에 붙어야할 값(자기 자신)을 다음 함수로 넘겨서 한자리씩 더해가면서 체크하는 방식이다.

여기서 중복된 소수들이 들어가는 것은 따로 체크하지 않았는데, Set을 활용해서 마지막에 중복된 숫자들을 없앤 배열을 만들고 그 길이를 return 하도록 했다.

코드

JavaScript

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;
}