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

프로그래머스 Level1 소수 만들기 문제

 

문제 풀이 : 주어진 배열의 요소에서 3개를 선택하여 만든 조합으로 소수 판별을 통해 

몇개의 소수가 만들어지는지 구하는 문제이다.

처음에 주어진 숫자중에 조합해서 3개를 만드는 경우의 수를 구해야 될거 같아서 수학의 "조합" 공식을 사용했다.

하지만 풀이 과정에서 그럴 필요가 없는것을 깨닫고 다시 풀었다.

 

문제의 예 nums[1,2,3,4] 에서 3개를 뽑을때 가능한 경우는 수는 4가지 경우이다.

[1,2,3], [1,2,4], [1,3,4], [2,3,4]  여기서 패턴을 찾으면된다.

배열의 길이를 n이라했을때, 0~n-2를 첫번째 인덱스, 1~n-1를 두번째 인덱스, 2~n를 세번째 인덱스로 지정하여

삼중 반복문을 돌리게되면 중복을 제외한 모든 경우의 수를 구할수있다.

 

그 후, 삼중 반복문을 통해 선택된 세개의 합을 소수 판별을 해주면된다.

소수 판별 알고리즘은 보통 2부터~n-1까지 반복문을 통해 나머지의 여부로 판별하는데,

이는 비효율적이므로 JS에서 제공하는 Math.sqrt 제곱근 메소드를 통해

2~제곱근 까지 반복문을 통해 소수 판별을 해주면된다. (위의 과정보다 연산횟수가 현저히 줄어든다.)

(하지만 시간복잡도는 둘다 O(n)이라서 의미는 없지만 그냥 가독성있게 짜봤다...)

 

function solution(nums) {
    var answer = 0;
    var array = [];
    var len = nums.length;
    
    for(let i=0; i<len-2; i++){
        for(let j=i+1; j<len-1; j++){
            for(let k=j+1; k<len; k++){
                array.push(nums[i]+nums[j]+nums[k]);
            }
        }
    }

    //reduce함수 이용
    answer = array.reduce((acc, cur, idx) => acc + primeNumber(cur),0)

    return answer;
}

//소수 판별 함수
function primeNumber(n){
    for(let i=2; i<= Math.sqrt(n); i++) {\
        //소수가 아닐 경우
       if(n%i == 0){
           return 0;
       }
	}
    //소수일 경우
    return 1;
}

 

* 삼중 반복문인 형태로 시간복잡도는 O(n^3)을 가진다.

조금 더 고민해본다면 시간복잡도를 줄일 수 있을것같다.

Level1인데 어려웠다....