103일차 - 프로그래머스 소수만들기

시험이 끝난 후 솔로데이에 공부할 것을 찾다가 머리를 식힐겸 프로그래머스 1단계를 풀었다.

그 중에서 정리할 것은 HA 조합과 연관이 되는 소수만들기 문제를 정리해 보려고 한다.

문제 : 주어진 숫자 중 3개의 수를 더했을 때, 소수가 되는 경우의 개수를 구하려고한다.
숫자들이 들어있는 배열 nums가 매개변수로 주어질때, 서로 다른 3개를 골라 더했을때 소수가 되는 경우의 갯수를 return하도록 solution 함수를 완성하시오.

입출력 예시

solution([1, 2, 3, 4]) // 1
solution([1, 2, 7, 6, 4]) // 4

이 문제는 숫자 중 3개의 수를 더한다는 조건이 있으므로 for문 3개를 중첩해서 사용해서 문제를 해결하면 매우 쉬워진다.
하지만 나는 만약 두 번째, 인자로 n 개를 골라라 라는 조건이 들어올 경우에도 해결할 수 있는 알고리즘을 만들고 싶어서, 조합을 사용하기로 했다.

조합을 사용하기 전에 소수를 판별할 알고리즘을 만들어 보자.
소수를 판별하는 가장 간단한 방법은 for문을 사용하는 것이다.

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

위와 같이 작성할 수 있다.
시간복잡도가 O(N)이다.

하지만 제곱근을 사용해서 시간 복잡도를 O(√ N)으로 만들 수 있다.

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

이 소수 판별을 사용해서 시간복잡도를 줄여보도록 하자.

알고리즘

// 위에서 작성한 소수 판별
function isPrime(num) {
  if (num === 2) return true;
  
  for (let i = 2; i <= Math.floor(Math.sqrt(num)); i++) {
    if (num % i === 0) return false;
  }
  
  return true;
} 

function solution(nums) {
    let answer = 0;

  // 조합
    function combination(n, bucket, arr) {
        if (n === 0) {
            if (isPrime(bucket)) {
                answer++;
            }        
            return;
        }
        
        for (let i = 0; i < arr.length; i++) {
            let choice = arr[i];
            let clone = arr.slice();
            
            aux(n - 1, bucket + choice, clone.slice(i + 1));
        }
    }
    
  // 문제가 배열중 숫자 3개만 선택을 하는 조건이어서 첫 번째 인자로 3을 넣었다. 
  // 만약 두 번째 인자로 매개변수 x를 입력한다고 했을때, combination(x, 0, nums)라고 작성하면 된다.
    combination(3, 0, nums)
    
    return answer;

}