알고리즘: 완전 탐색>소수 찾기

링크: https://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은 같은 숫자로 취급합니다.

---

📒 문제 풀이에 앞서,

이 문제는 '순열'과 '에라토스테네스의 체'를 알아야 쉽게 접근이 가능했다.

처음에는 순열이라는 개념을 생각하지 않고, for문을 돌려 문제를 해결하려고 하였지만 어려움이 많아 순열의 개념에 대해 학습하고 다시 문제에 도전하게 되었다.

순열

링크: https://velog.io/@proshy/JS순열조합중복순열-구하기
순열: 순서대로 뽑아서 줄을 세우는 것
순열의 코드는 다음과 같다.

function permutation(arr, selectNum) {
  let result = [];
  // selectNum이 1이면 arr 각 자신들만 return 해주면 된다.
  if (selectNum === 1) return arr.map((v) => [v]);

  arr.forEach((v, idx, arr) => {
    const fixer = v;
    // 현재 arr에서 돌아가고 있는 v값을 제외한 나머지 배열을 resArr에 저장
    const restArr = arr.filter((_, index) => index !== idx);
    // 재귀함수 사용해 반복되는 부분을 처리
    const permuationArr = permutation(restArr, selectNum - 1);
    // 고정된 fixer 값을 기준으로 v값들을 한 배열에 넣기
    const combineFixer = permuationArr.map((v) => [fixer, ...v]);
    result.push(...combineFixer);
  });
  return result;
}

소수 구하기

• 에라토스테네스의 체 사용
  
  코드는 다음과 같다.

// true로 가득 채워진 빈 배열 생성(0부터 시작하기에 n+1 범위를 사용)
let primeNumbers = new Array(n + 1).fill(true);
for (let i = 0; i * i <= n + 1; i += 1) {
  // 0,1은 소수가 아니다
  i < 2 && (primeNumbers[i] = false)
  // 자신이 소수일 때,
  if (primeNumbers[i]) {
    // for문을 돌려서,
    for (let j = i * i; j <= n + 1; j += i) {
      // 자신의 배수들을 모두 false로 만든다.
      primeNumbers[j] = false;
    }
  }
}

이렇게 두 기반 지식을 가지고 드디어 소수 찾기 문제를 풀어 볼 시간이다.

✅ 소수 찾기(level.2)

간략하게 설명하자면

• numbers를 모두 쪼개서 배열에 넣고, 이 배열을 순열을 통해 모든 경우의 수를 구해주었다.

• 이렇게 나온 결과는 [["1","2"],["1","3]]과 같이, 배열과 문자로 되어있었는데,
  join()을 통해 배열 내부의 문자들을 합치고
  Number()메서드를 통해 이러한 문자들을 숫자로 변환해 주었다.

• 이러한 수들을 에라토스테네스 체와 비교하여 소수를 찾아주었다.

• 저장된 배열에는 중복된 값들이 들어있었는데, set을 통해 중복을 없애주고,
  .size로 set의 길이를 구해, 결과를 return 해주었다.

코드는 다음과 같다.(주석 첨부되어있음)

function solution(numbers) {
    // numbers 쪼개기
    numbers = numbers.split('')
    let answer = [];

    // 순열을 통한 결과값 구하기
    function permutation(arr, selectNum) {
        let result = [];
        if (selectNum === 1) return arr.map((v) => [v]);
        arr.forEach((v, idx, arr) => {
            const fixer = v;
            const restArr = arr.filter((_, index) => index !== idx);
            const permuationArr = permutation(restArr, selectNum - 1);
            let combineFixer = permuationArr.map((v) => [fixer, ...v]);
            result.push(...combineFixer);
        });
        return result;
    }
    // 반복문을 통해 조각을 합치는 개수에 따른 결과값들을 배열에 저장
    let piece = []
    for (var i = 1; i <= numbers.length; i++) {
        piece.push(permutation(numbers, i))
    }
    // 순열로 나온 경우의 '문자 배열'들을 '숫자'로 바꾸어주는 작업
    for (var i = 0; i < piece.length; i++) {
        for (var j = 0; j < piece[i].length; j++) {
            answer.push(Number(piece[i][j].join('')))
        }
    }

    // 소수를 찾는 범위를 max값으로 한정시키기 위해 max값 구하기
    let max = answer.reduce((acc, cur) => acc > cur ? acc : cur)
    // 소수 구하기(에라토스테네스의 체)
    let primeNumbers = new Array(max + 1).fill(true);
    for (let i = 0; i * i <= max + 1; i += 1) {
        i < 2 && (primeNumbers[i] = false)
        if (primeNumbers[i]) {
            for (let j = i * i; j <= max + 1; j += i) {
                primeNumbers[j] = false;
            }
        }
    }
    // 구한 값이 소수인지 확인하는 작업
    answer = answer.filter(a => primeNumbers[a] === true)
    // 중복 값 제거, 뒤늦게 넣어준 이유는 set 상태에서 여러 메서드들 사용 불가하기 때문에
    answer = new Set(answer)
    return answer.size
}