프로그래머스 [소수 찾기]

소수 찾기

소수

• 특정한 수가 있다면, 1부터 해당 수까지 중에서 나누어 떨어지는 수가 1과 자기 자신만 존재하는 수를 의미한다.

로직

• 흩어진 종이 조각에 각 수가 1자리씩 입력이 되어있다. 따라서 해당 수를 먼저 1개씩 분리하여 배열에 저장할 필요가 있다.
• 입출력 예시를 보니, 흩어진 종이 조각 중 1개만 뽑아서 소수인지 검사하는 경우도 존재한다.
• 따라서 흩어진 종이 조각들 중 1개를 순서가 의미가 있게 뽑는 경우부터, 흩어진 종이 조각들 갯수만큼 뽑는 경우까지 고려해야한다.
• 즉 정리하자면, 흩어진 종이 조각들 중 1개부터 흩어진 종이 조각들 갯수까지, 순서가 의미가 있게 뽑고 뽑은 목록을 순회하며 요소가 이미 검사한 수인지 검사한 뒤, 소수인지 검사하여 소수가 맞다면 answer 목록에 넣는다.

순열

• 순서에 따라 뽑은 요소의 가치 또는 의미가 달라지는 개념이라 생각하면 된다.
• 아래처럼 작성하여 이용하였다.

    function permutations(arr, n) {
  // 1개만 뽑는다면 그대로 순열을 반환한다. 탈출 조건으로도 사용된다.
  if (n === 1) return arr.map((v) => [v]);
  let result = [];

  // 요소를 순환한다
  arr.forEach((fixed, idx, arr) => {
    // 현재 index를 제외한 요소를 추출한다.
    // index번째는 선택된 요소
    const rest = arr.filter((_, index) => index !== idx);
    // 선택된 요소를 제외하고 재귀 호출한다.
    const perms = permutations(rest, n - 1);
    // 선택된 요소와 재귀 호출을 통해 구한 순열을 합쳐준다.
    const combine = perms.map((v) => [fixed, ...v]);
    // 결과 값을 추가한다.
    result.push(...combine);
  });

  // 결과 반환
  return result;
}

소수 검사

• 1부터 자기 자신까지 차례대로 나눠보며 나눠 떨어지는 수가 1과 자기 자신만 존재하는지 검사한다.
• 하지만 1부터 끝까지 순회하면, 시간복잡도가 O(n)으로 복잡도가 꽤 커서 줄일 필요가 있다.
• 아래와 같이 작성하자.

    function isPrime(num) {
    for (let i = 2; i * i <= num; i += 1) { // 이 부분이 변경됩니다.
        if (num % i == 0) {
            return false;
        }
    }

    return true;
}

특정 수에 대해서 제곱근까지만 나눠 떨어지는지 검사하고, 그 이상은 검사할 필요가 없다.
위와 같이 작성하여 시간복잡도를 O(sqrt(n))으로 줄일 수 있다.

최종 코드

function solution(numbers) {
    const arr = numbers.split('')
    let loop = 0

    function isPrime(num) {
    for (let i = 2; i * i <= num; i += 1) { // 이 부분이 변경됩니다.
        if (num % i == 0) {
            return false;
        }
    }

    return true;
}
    
    function permutations(arr, n) {
  // 1개만 뽑는다면 그대로 순열을 반환한다. 탈출 조건으로도 사용된다.
  if (n === 1) return arr.map((v) => [v]);
  let result = [];

  // 요소를 순환한다
  arr.forEach((fixed, idx, arr) => {
    // 현재 index를 제외한 요소를 추출한다.
    // index번째는 선택된 요소
    const rest = arr.filter((_, index) => index !== idx);
    // 선택된 요소를 제외하고 재귀 호출한다.
    const perms = permutations(rest, n - 1);
    // 선택된 요소와 재귀 호출을 통해 구한 순열을 합쳐준다.
    const combine = perms.map((v) => [fixed, ...v]);
    // 결과 값을 추가한다.
    result.push(...combine);
  });

  // 결과 반환
  return result;
}
    const answer = []
    
    while(loop <= arr.length) {
        loop += 1
        const permutataionLoop = permutations(arr, loop)
        for(let i = 0; i < permutataionLoop.length; i++) {
           const number = Number((permutataionLoop[i].reduce((sum, acc) => sum + acc)),'')
           if(number >= 2 && !answer.includes(number)) {
               if(isPrime(number)) {
                   answer.push(number)
               }
           }
        }
    }
    return answer.length
}

• 정리하자면 위 최종 코드는 다음과 같이 요약할 수 있다.
  • numbers의 각 숫자를 분리한다.
  • 뽑는 자릿수를 나타내는 loop 변수를 이용하여 numbers의 최대 자릿수(흩어진 종이 조각 갯수) 까지 반복을 시행한다.
  • 매 반복마다 수행하는 동작은 뽑는 자릿수만큼 순열 알고리즘을 통해 뽑고, 해당 목록을 순회하며 요소가 answer 배열에 존재하지 않는다면, 소수인지 검사하여 소수이면 정답에 넣는다.(1은 어차피 소수가 아니기 때문에 고려하지 않는다.)
  • 정답의 갯수(길이)를 반환한다.