[프로그래머스 JS] - 소수 만들기 (Feat. 조합, 재귀함수)

 

정말 오랜만에 블로그를 재가동시키려고 한다.

 

근무를 하는 동안 많은 일이 있었고
조금의 회복할 시간도 필요해서 휴식을 취했는데

다시 공부시작합니다..!!

빠이팅

 

그 시작은 프로그래머스 레벨1 문제 전부 풀기 !

 

현재 79문제 중 60문제 풀었고 

그 과정에서 재귀함수를 꽤나 유용하게 사용하고 있어서 

공유해볼까 한다.

 

 

 

 

 

 

    const handleCombinations = (arr, start) => {
        if (arr.length === 3) {
            const resultNumber = arr[0] + arr[1] + arr[2]
            if(getResult(resultNumber)) answer++;
            return;
        }
        
        for (let i = start; i < nums.length; i++) {
            handleCombinations([...arr, nums[i]], i + 1)
        }
    }

 

handleCombinations 함수는 for문 안에서 본인(함수)을 반복하여 호출한다.

 

이렇게 호출할 경우 

arr이 빈배열에서 시작하여 하나의 값을 고정 후
그 외의 값을 추가로 삽입하여 모든 경우의 수를 만든다.

 

[1, 2, 3, 4]라는 배열이 nums로 받아지는 경우

 

위와 같은 형태로 모든 경우의 수를 확인할 수 있다.

우리가 원하는 배열의 길이는 3이므로

배열의 길이가 3일 때 해당 배열의 합을 구하여 

 

소수를 구하는 getResult()함수를 호출하고 그 값이 소수일 때 true로 반환받는다.

 

const getResult = (number) => {
    for(let i = 2; i <= Math.sqrt(number); i++){
        if(number % i === 0){
            return false;
        }
    }
    return true;
}

 

위 코드는 에라토스테네스의 체라는 알고리즘을 이용하여 소수 여부를 확인한다.

 

매개변수 number를 받은 후 해당 매개변수가 소수인지 아닌지 판별하는데

매개변수의 제곱근까지만 반복문을 돌아도 소수여부를 확인할 수 있기 때문에

반복되는 횟수가 급감한다.

 

당연히 런타임도 줄어들게 된다.

 

 

재귀함수는 무슨 개념인지만 알고 사용해보진 못했는데

경우의 수를 구할 때 정말 유용하게 사용될 것 같다.