programmers - 소수 만들기

문제 설명

주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요.

제한사항

∙ nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다.
∙ nums의 각 원소는 1 이상 1,000 이하의 자연수이며, 중복된 숫자가 들어있지 않습니다.

입출력 예 설명

입출력 예 #1
[1,2,4]를 이용해서 7을 만들 수 있습니다.

입출력 예 #2
[1, 2, 4]를 이용해서 7을 만들 수 있습니다.
[1, 4, 6]을 이용해서 11을 만들 수 있습니다.
[2, 4, 7]을 이용해서 13을 만들 수 있습니다.
[4, 6, 7]을 이용해서 17을 만들 수 있습니다.

function solution(nums) {
    let answer = [];
    let combinations = [];
    let i = 0;
    
    while( i < nums.length){
        for( let j = i + 1; j < nums.length; j++){
            for(let x = j + 1; x < nums.length; x++ ){
                if(combinations.indexOf( nums[i] + nums[j] + nums[x] ) < 0){
                    combinations.push(nums[i] + nums[j] + nums[x]);
                }
            }
        }
        i++;
    }

    for(let x = 0; x < combinations.length; x++){
        let count = 0;
        for(let y = 1; y <= combinations[x]; y++ ){
            if( combinations[x] % y === 0){
                count++;
            }
        }

        if(count === 2){
            answer.push(combinations[x]);
        }
    }
    
    return answer.length;
}

반복문 3개를 돌려서 가능한 3자리수 조합을 구한다. 하지만 한 두 개의 3자리수 케이스 누락이 발생하여 정확성이 떨어진다. 중복된 숫자가 없기 때문에 combinations 배열에 indexOf를 쓸 필요가 없다.

function solution(nums) {
    let answer = [];
    let combinations = [];
    let i = 0;
    
    while( i < nums.length){
        for( let j = i + 1; j < nums.length; j++){
            for(let x = j + 1; x < nums.length; x++ ){
            	combinations.push(nums[i] + nums[j] + nums[x]);
            }
        }
        i++;
    }

    for(let x = 0; x < combinations.length; x++){
        let count = 0;
        for(let y = 1; y <= combinations[x]; y++ ){
            if( combinations[x] % y === 0){
                count++;
            }
        }

        if(count === 2){
            answer.push(combinations[x]);
        }
    }
    
    return answer.length;
}

아래는 비슷하지만 연산시간이 줄어든 다른 사람의 풀이

function solution(nums){
  let count = 0;
  let temp = [];
  for(let i = 0; i < nums.length; i++){
    for(let j = i + 1; j < nums.length; j++){
      for(let k = j + 1; k < nums.length; k++){
        let sum = nums[i] + nums[j] + nums[k];
        temp.push(sum);
      }
    }
  }

  for(let l = 0; l < temp.length; l++){
    if(primeNumber(temp[l])){
      count++;
    }
  }
  return count;
}


function primeNumber(nums){
  for(let i = 2; i * i <= nums; i++){
    if(nums % i === 0) return false;
  }
  return true;
} // 소수판별 함수 버전1 => N의 약수는 제곱근 N의 범위에 존재
    
function primeNumber(nums){
    let count = 0;
    for(let i = 1; i <= nums; i++){
        if(nums % i === 0) count++;
    }
    if(count === 2){
        return true;
    }else if( count > 2){
        return false;
    }
} // 소수판별 함수 버전2 => 기존에 알았던 방식
    

참고)
https://velog.io/@diddnjs02/코딩테스트프로그래머스-소수-만들기
https://jm-park.github.io/algorithm/2018/08/06/Prime-Number(소수)-판별법-알고리즘.html

+) python version

def solution(nums):
    answer = []
    combinations = []
    i = 0
    
    while i < len(nums):
        for j in range(i + 1, len(nums)):
            for x in range(j + 1, len(nums)):
                combinations.append(nums[i] + nums[j] + nums[x])
        i += 1
    

    
    for x in range(0, len(combinations)):
        count = 0
        for y in range(1, combinations[x] + 1):
            if combinations[x] % y == 0:
                count += 1
                
        if count == 2:
            answer.append(combinations[x])

    return len(answer)

from itertools import combinations 
def check(a, b, c): 
    total = a + b + c
    for i in range(2, total): 
        if total % i == 0 : return False 
    return True 

def solution(nums):
    answer = 0
    A = list(combinations(nums, 3))
    for i in A: 
        if check(i[0], i[1], i[2]): answer += 1
    return answer

from itertools import combinations
import math
def solution(nums):
    candidates = combinations(nums, 3)
    answer = 0
    for item in candidates:
        sums = sum(item)
        is_prime = True
        for i in range(2, int(math.sqrt(sums)) + 1): // N의 약수는 해당 제곱근 범위에 있음
            if sums % i == 0:
                is_prime = False
                break
        if is_prime:
            answer += 1
    return answer
    

참고)
https://eda-ai-lab.tistory.com/493
https://inspirit941.tistory.com/entry/Python-프로그래머스-소수-만들기-Level-2