1. 소수 찾기

숫자가 적힌 종이 쪼가리가 주어진다. 이 종이쪼가리를 이어붙여서 숫자를 만들 수 있는 만큼 만들고 그 이어붙인 숫자들이 소수이면 answer에 추가한다. 예를들어, 17 이 주어지면 1,7이라는 숫자가 적힌 종이조각이 주어진것이다.

이때 만들수 있는 경우의 수는 1,7,17,71이다. 이중에 소수를 찾아서 return하면 된다.

2. 접근 방법

뽑아낼 수 있는 모든 경우를 뽑아내는 것에서 부분집합이 떠올랐다. 그러나 부분집합은 순서를 고려하지 않는다. 즉, 1,7,17만을 뽑아 내는 것이다. 7이 앞으로가고 1이 뒤로가서 71을 뽑아내지는 않는다.

숫자의 갯수와 순서까지 신경써서 모든 경우의 수를 뽑아내는 것을 brute-force라고 하나? 여튼 부분집합, 소수 판별법 까지 구현했지만 숫자를 뒤집어서까지 경우의 수를 뽑아내는 기능은 구현하지 못해서 정답을 봤는데 역시나가 역시나다. 그냥 좋다.

• pseudo code
  • numbers의 숫자를 하나하나 배열에 넣는다
  • 숫자의 조합이 이미 만들어진 숫자의 조합인지 판별하기 위해 nums Set을 만든다
  • 재귀함수를 만들고, 각 숫자를 차례로 앞에다 넣고 뒤에다 넣고 그러면서 조합을 만들어간다.
    • 1,7 / 7,1처럼 말이다
  • 그러고 숫자의 조합이 만들어지면 nums Set안에 존재여부를 확인한 뒤 없으면 저장한다.
  • 그리고 소수인지의 여부를 판별한뒤에 맞으면 answer를 증가시킨다.

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

  return n > 1;
}

function solution(numbers) {
  let answer = 0;
  let n = numbers.split("");
  let nums = new Set();
  combi(n, "");

  function combi(arr, strNum) {
    // 문자형태의 숫자가 만들어 졌다면
    if (strNum.length > 0) {
      if (nums.has(Number(strNum)) === false) {
        nums.add(Number(strNum));
        if (isPrime(strNum)) {
          answer++;
        }
      }
    }
    if (arr.length > 0) {
      for (let i = 0; i < arr.length; i++) {
        // arr안에 있는 숫자를 뜯어내서 조합하기 위새 새로운 arr , cut을 만들었음
        let cut = arr.slice(0); // 새로운 array에 담음 ==> ['1','7']
        // 차례대로 뜯어내서 하나씩 조합
        cut.splice(i, 1); // i가 0일때 결과적으로 ['7']만 남음. ['1','7'] 중에서 '1'을 떼어가므로
        combi(cut, strNum + arr[i]); // combi(['7'],''+'1')
      }
    }
  }

  return answer;
}

보기 쉽게 그림으로 정리해 보았다.

보면, ['1','7']이 주어졌다고 했을 때, 맨처음 level에서는 왼쪽가지에서는 1로 시작되는 숫자의 조합이 나타나고 오른쪽 가지는 7로 시작되는 조합이 나타날것이다. 그런식으로 뻗어가면서 앞뒤로 붙여나가고 그럴 것이다.

다시 배웠다. 재밌다. 좋다. 신기하다!