소수 만들기(프로그래머스 12977)

Siwoo Pak·2021년 12월 21일
0

자료구조&알고리즘

목록 보기
36/38

코드 풀이

// 조합으로 배열의 모든 경우의 수 구하기(시간복잡도는 O(2^N))
const getCombinations = (arr, n) => {
    const results = [];
    // n이 1이 되는 경우는 현재값을 선택하는 것과 동일
    // 따라서 각각의 원소를 바로 배열 형태로 리턴
    // 재귀호출에서 n이 1이 되는 순간부터 배열 데이터 생성
    // 즉 1부터 역으로 다시 거슬러 올라가 n이 될때까지
    // 선택된 원소들로 배열(조합)을 구성
    if (n === 1) return arr.map((el) => [el]); 
    
    // 처리할 현재 요소, 현재 요소의 인덱스, 배열
    arr.forEach((fixed, index, origin) => {
      // 처리할 현재 요소를 제외한 배열  
      const rest = origin.slice(index + 1);
      // 만약 제외한 배열의 길이가 selectNumber-1보다 작다면 반복문 취소  
      if(rest.length < n-1) return false;
      // 제외한 배열의 조합 구하기 (재귀)  
      const combinations = getCombinations(rest, n - 1); 
      // 현재요소와 조합으로 구한 배열 합쳐서 배열로 리턴
      const attached = combinations.map((el) => [fixed, ...el]); 
      // result에 각 요소를 담아준다  
      results.push(...attached); 
    });

    return results; // 결과 담긴 results return
}

// 조합의 각 요소들의 합을 구해서 배열로 리턴(시간복잡도: O(N))
const getSums = (arr) => {
// 이중 배열이기때문에 해당 배열의 요소의 배열합을 map, reduce 함수를 사용하여 구함
    const sums = arr.map(el => {
       const sum = el.reduce((acc, cur) => acc+cur)
       return sum;
    })
    return sums;
}

// 소수판별하기(시간복잡도는 O(√N))
const isPrime = (n) => {
    for (let i = 2; i <= Math.sqrt(n); i++) {
      if (n % i === 0) return false;
    }

    return true;
}

// 결과적으로 시간복잡도는 O(2^N)
function solution(nums) {
    // 배열에서 중복되지 않는 3개의 수의 조합을 구하고 
    // 그 조합의 배열인 요소의 합을 요소로 가진 배열 구하기
    let combination = getSums(getCombinations(nums,3));

    // 그 배열의 요소가 소수인 개수 구하기
    let answer = combination.reduce((acc, cur) => acc + isPrime(cur),0)
    
    return answer;
}
profile
'하루를 참고 인내하면 열흘을 벌 수 있고 사흘을 참고 견디면 30일을, 30일을 견디면 3년을 벌 수 있다.'

0개의 댓글