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

문제 설명

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

각 종이 조각에 적힌 숫자가 적힌 문자열 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은 같은 숫자로 취급합니다.

---

풀이 과정

소수를 구하는게 문제가 아니라…
모든 숫자들의 순열 조합들을 구하는게 굉~~장히 까다로웠다.

1. 순열과 조합을 생성하기 위한 헬퍼 함수를 만든다.
2. 그리고 numbers의 모든 순열조합을 중복 없이 사용하기 위한 Set을 생성해 사용한다.
3. Set을 통해 모든 순열조합들의 소수여부를 판별한다.

---

소스 코드

function solution(numbers) {
  let answer = 0;
  const numArr = [...numbers];
  const numSet = new Set();
  function permutation(nums, numString) {
    if (!nums.length) return numSet.add(Number(numString));
    nums.forEach((num, i) => {
      // nums를 깊은 복사! (splice에 의해 원본 배열이 변경되는 것 방지)
      let copy = [...nums];
      copy.splice(i, 1); // temp에서 i번째 요소를 제거
      permutation(copy, numString + num); // 재귀 시작(잘린 배열, '넘겨진 숫자'+'위에서 빠진 놈')
    });
    return numSet.add(Number(numString));
  }
  permutation(numArr, '');
  const allCombinations = Array.from(numSet);
  allCombinations.forEach((num) => (answer += isPrimeNum(num) ? 1 : 0));
  return answer;
}

function isPrimeNum(num) {
  // 소수를 찾을 때에는 타겟넘버의 제곱근 까지만 판별해도 된다고 한다.
  for (let i = 2; i <= Math.sqrt(num); i++) {
    // 순회를 하다가 단 하나라도 i로 나눴을 때 0으로 나누어 떨어지면 이 숫자는 소수가 아니다.
    if (Number(num) % i === 0) return false;
  }
  return 2 <= Number(num); // 넘어온 num 자체가 0 또는 1일 수 있으므로 이와 같이 처리.
}

permutation 헬퍼함수 설명

// 입력 예시 : nums = [1,0,3]

//#1
function permutation(nums, numString) {
    if (!nums.length) return numSet.add(Number(numString));
		// 1.처음에 [1,0,3],''가 매개변수 값으로 들어온다.
    nums.forEach((num, i) => {
      let copy = [...nums]; // 2.깊은 복사를 한다.
      copy.splice(i, 1); // 3.i번째 값을 잘라낸다. (i=0 -> [0,3])
      permutation(copy, numString + num); // 재귀함수를 실행시킨다. ([0,3], ''+'1')
    });
    return numSet.add(Number(numString));
  }
  permutation(numArr, "");
}

//#2
function permutation(nums, numString) {
    if (!nums.length) return numSet.add(Number(numString));
		// 1.이번엔 [0,3],'1'이 매개변수 값으로 들어온다.
    nums.forEach((num, i) => {
      let copy = [...nums]; // 2.깊은 복사를 한다.
      copy.splice(i, 1); // 3.i번째 값을 잘라낸다. (i=0 -> [3])
      permutation(copy, numString + num); // 재귀함수를 실행시킨다. ([3], '1'+'0')
    });
    return numSet.add(Number(numString));
  }
  permutation(numArr, "");
}

//#3
function permutation(nums, numString) {
    if (!nums.length) return numSet.add(Number(numString));
		// 1.이번엔 [3],'10'이 매개변수 값으로 들어온다.
    nums.forEach((num, i) => {
      let copy = [...nums]; // 2.깊은 복사를 한다.
      copy.splice(i, 1); // 3.i번째 값을 잘라낸다. (i=0 -> [])
      permutation(copy, numString + num); // 재귀함수를 실행시킨다. ([], '10'+'3')
    });
    return numSet.add(Number(numString));
  }
  permutation(numArr, "");
}

//#4
function permutation(nums, numString) {
		// 이번엔 nums가 위에서 []로 넘어왔기 때문에 아래 조건문에 걸린다.
		// 따라서 현재의 numString값을 Set에 add해준다.
    if (!nums.length) return numSet.add(Number(numString));
}// 그럼 이제 그 다음 콜스택인 [0,3], '1'이었던 때로 돌아간다. forEach문으로!

//#5
function permutation(nums, numString) {
    if (!nums.length) return numSet.add(Number(numString));
		// 1.위에서 실행시켰던 #2으로 되돌아 온 것이다. 동일하게 [0,3],'1'이다.
    nums.forEach((num, i) => {
      let copy = [...nums]; // 2.깊은 복사를 한다.
      copy.splice(i, 1); // 3.이번엔 i가 1 더해진 상태이기 때문에 i=1이다 (위에서 0 실행했음)
      permutation(copy, numString + num); // 재귀함수를 실행시킨다. ([0], '1'+'3')
    });
    return numSet.add(Number(numString));
  }
  permutation(numArr, "");
}

//#6
function permutation(nums, numString) {
    if (!nums.length) return numSet.add(Number(numString));
		// 1.이번엔 [0],'13'이 매개변수 값으로 들어온다.
    nums.forEach((num, i) => {
      let copy = [...nums]; // 2.깊은 복사를 한다.
      copy.splice(i, 1); // 3.i번째 값을 잘라낸다. (i=0 -> [0])
      permutation(copy, numString + num); // 재귀함수를 실행시킨다. ([], '13'+'0')
    });
    return numSet.add(Number(numString));
  }
  permutation(numArr, "");
}

//#7
function permutation(nums, numString) {
		// 이번엔 [],'130'이 매개변수 값으로 들어왔으나, nums의 length가 0이다.
		// 따라서 아래 조건에 걸리기 때문에 '130'을 Set에 add 해준다.
    if (!nums.length) return numSet.add(Number(numString));
}

// #8 => 이하는 생략하도록 하겠다.
// #2의 forEach문이 이제 다 돈 것이기 때문에, 이제 #1의 forEach문으로 (i=1) 돌아가면 된다.

---