소수 찾기

소수 찾기

오래간만에 자바스크립트 제네레이터를 쓸 수 있는 문제가 나와서 블로그에 스크랩해둔다.

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42839

문제 설명

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

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

제한사항

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

입출력 예

numbers	return
“17”	3
“011”	2

입출력 예 설명

예제 #1 [1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

예제 #2 [0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

11과 011은 같은 숫자로 취급합니다.

풀이

문제 자체는 별 거 없다. 주어진 숫자로 만들 수 있는 모든 숫자를 만들어서 소수인지 판별하면 된다. 내가 자랑하고 싶은 건 그 “모든 숫자”를 만들어내는 로직이다. 아래 numgen 제네레이터 참고.

function isPrime(n) {
  if (n < 2) return false;
  if (n === 2) return true;
  if (n % 2 === 0) return false;
  for (let i = 3; i <= Math.floor(Math.sqrt(n)); i += 2) {
    if (n % i === 0) return false;
  }
  return true;
}

function* numgen(head, rest) {
  if (head.length > 0) yield Number(head.join(""));
  for (let i = 0; i < rest.length; i++) {
    const rest2 = [...rest];
    const num = rest2.splice(i, 1)[0];
    yield* numgen([...head, num], rest2);
  }
}

function solution(numbers) {
  const cards = [...numbers];
  const found = new Set();

  const gen = numgen([], cards);
  for (const n of gen) {
    if (isPrime(n)) found.add(n);
  }
  return found.size;
}

순열 생성하는 알고리즘보다 좀 더 직관적으로 작성이 가능하다. numgen 제네레이터는 head에는 이미 선택된 숫자들을, rest에는 아직 선택되지 않은 숫자들을 받는다. head에 숫자가 있으면 그 숫자들을 합쳐서 숫자로 만들어서 yield하고, rest에 숫자가 있으면 그 숫자를 하나씩 뽑아 head에 넣고 재귀호출(위임)한다. 이렇게 하면 numgen 제네레이터는 numbers로 만들 수 있는 모든 숫자를 만들어낸다.

문제는, 카드 자체에 중복 숫자가 있기 때문에 numgen스스로도 중복된 순열을 만들어낸다는 것이다. 예를 들어 numbers가 011이면 numgen은 011 이라는 숫자를 두 번 만들어낸다. 각 카드를 순서대로 a=0, b=1, c=1 이라고 했을 때 [a,b,c] 와 [a,c,b] 모두 011 이기 때문이다. 더 안좋은 점은 문제에도 설명했다시피 011과 11은 같은 숫자로 취급한다는 것이다. 이 중복을 반드시 처리해야만 한다.

숫자를 생성할 때 필터하는 방법도 있지만 나는 소수 판별 알고리즘이 Set을 탐색하는 것보다 빠를 것이라고 판단해 같은 숫자를 중복 검사하는 오버헤드를 감수하고, 발견한 소수들만을 Set에 집어넣었다. 이렇게 중복을 제거하고 발견한 소수의 숫자를 리턴하도록 만들어 문제를 해결했다.

즉, 이 로직은 소수의 갯수 뿐만 아니라 소수 그 자체의 리스트도 알고 있다. 조금 오버엔지니어링된 것 같은 느낌이지만 코드를 현저히 복잡하게 만들지 않으면서 최대한 깔끔하게 풀 수 있는 해법이라고 생각해 선택했다.

여기서 더 나아간다면 소수 판별기에 dp를 적용해서 이미 찾은 소수의 리스트를 기억하고 그걸 먼저 테스트하는 방법도 있을 것이다. 하지만 문제의 제한 사항에 언급된 바대로, numbers의 길이가 최대 7 즉 아무리 커봤자 1천만(9,999,999)을 넘지 않는 수이다. 심지어 1천만 이하의 모든 소수를 미리 계산해서 판별하는 방법도 쓸 수 있다(이 방법이 가장 빠를 것이다). 그러나 이 문제는 “완전탐색” 을 묻는 문제였고 내가 강조하고자 하는 해법도 자바스크립트 제네레이터를 사용한 해법이므로 이 정도에서 마무리하고자 한다.