[프로그래머스] 소수 만들기

[ 문제 ]

이 문제를 설명하자면, 배열인 nums에 들어있는 숫자 중, 서로 다른 3개를 골라 더하여 소수가 되는 경우의 개수를 return하는 것이다.

- 입출력 예시로 설명을 하면, nums가 [1,2,3,4]이면 서로다른 3개를 골라 소수가 되는 경우는 [1,2,4] === 7, 하나의 경우밖에 없기때문에 1이 return 됩니다.

 

 

[ 풀이 ]

1/ 먼저 소수인지를 판별하는 함수를 하나 만든다.

2/ 반복문을 이용하여 nums의 서로 다른 3개의 수를 더한다.

3/ 1번에서 만든 소수판별함수에 넣어 소수인지 확인한다.

 

 

 

1/ 먼저 소수인지를 판별하는 함수를 하나 만든다.

function isPrime(num){
    for(let i = 2; i <= Math.sqrt(num); i++){
 //num이 아닌 Math.sqrt(num)까지만 반복문을 돌리는 이유는 시간복잡도를 줄이기 위해서이다.
 //제곱근을 기준으로 약수들이 대칭적으로 곱셈이 일어나기 때문입니다.
 //따라서, 제곱근보다 작은 수로도 나누어지지않으면, 제곱근보다 큰 수로도 나누어지지않고,
 //제곱근보다 작은 수로 나누어떨어지게되면, 대칭적으로 곱해지는 수로도 나누어떨어지게된다.
 
         if(num % i === 0) { //1을 제외한 그 어떠한 수로 나누어떨어지면 소수가 아니다.
           return false;
          } 
    } return true; //반복문을 다 돌려도 나누어떨어지는게 
 }

 

 

2/ 반복문을 이용하여 nums의 서로 다른 3개의 수를 더한다.

3/ 1번에서 만든 소수판별함수에 넣어 소수인지 확인한다.

 

function solution(nums) {
//소수판별함수
     function isPrime(num) {
  for(let i = 2; i <= Math.sqrt(num); i++){
    if(num % i === 0){
      return false; 
    }
  }
  return true; 
} 

    let count = 0; 
    //먼저 count변수를 선언하고 0을 할당한다. 세 수를 합하여 소수일때 1씩 증가시킨다.
    //즉, 소수의 개수를 나타내는 변수.
    for(let i = 0; i < nums.length-2; i++){ // 가장 첫번째 수 ex: nums[0]
        for(let j = i+1; j < nums.length-1; j++){ //두번째 수 ex: nums[1]
            for(let t = j+1; t < nums.length; t++){ //세번째 수 ex: nums[2]
                if(isPrime(nums[i]+nums[j]+nums[t])){ //세 수를 더하여 소수판별함수에 넣는다.
                    count++; //만약 소수이면 count에 1을 추가한다.
                }
            }
        }
    }
    return count; //소수의 개수인 count를 반환.
   }