[JavaScript] 프로그래머스 재귀 문제 : 소수 만들기

문제 요구사항

프로그래머스 재귀 문제 Lv.1 소수 만들기

​

주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다.

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

​

제한 사항

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

​

입출력 예

nums	return
[1,2,3,4]	1
[1,2,7,6,4]	4

​

성공 코드​

보통 3중 for문을 이용해서 푸는데, 그 방법 보다는 재귀로 풀고싶어서 여러 가지 시도를 해보았다.

도저히 재귀로 풀 방법이 생각나지 않아서 GPT의 도움을 받아서 풀었다.

​

코드별 설명

1. 주어진 숫자가 소수인지 아닌지 구하는 함수

function isPrime(num) {
        if (num <= 1) return false;
        for (let i = 2; i * i <= num; i++) {
            if (num % i === 0) return false;
        }
        return true;
    }

약수에는 짝이 있기 때문에, 특정 수의 제곱이 num보다 작을 때까지 비교하며 특정 수가 약수인지 아닌지 찾는다.

Ex) 64 -> 64의 약수는 1 x 64, 2 x 32, 8 x 8 이므로 32까지 가지 않아도 2에서 약수가 있음이 검출된다.

​

2. 재귀 함수

// 조합을 재귀적으로 생성하고, 그 합이 소수인 경우를 계산하는 함수
    function findCombinations(index, selected, sum) {
        if (selected.length === 3) {
            if (isPrime(sum)) count++;
            return;
        }

        // 현재 전달 받은 index + 1, 현재 전달받은 배열에 현재 인덱스 값 추가해서 함수 호출
        // 전달한 배열의 길이가 3이면 return 되어 i가 더해짐
        for (let i = index; i < nums.length; i++) {
            findCombinations(i + 1, [...selected, nums[i]], sum + nums[i]);
        }
    }

index, selected, sum 세 개의 매개변수를 갖는다.

index -> 전체 nums의 인덱스 중 현재 가르키고 있는 인덱스

seleted -> 선택된 숫자들이 들어있는 배열

sum -> seleted 배열에 있는 숫자들의 합

​

seleted 안에 숫자가 3개라면 3개 숫자 합이 소수인지 아닌지 판별한다.

안에 들어있는 숫자가 3개가 아니라면, 다음 인덱스의 값을 추가하여 또 다시 함수를 호출한다.

이를 그림으로 정리해보면 아래 그림과 같다.

​

전체 코드

function solution(nums) {
    let count = 0;

    // 주어진 수가 소수인지 판별하는 함수
    function isPrime(num) {
        if (num <= 1) return false;
        for (let i = 2; i * i <= num; i++) {
            if (num % i === 0) return false;
        }
        return true;
    }

    // 조합을 재귀적으로 생성하고, 그 합이 소수인 경우를 계산하는 함수
    function findCombinations(index, selected, sum) {
        if (selected.length === 3) {
            if (isPrime(sum)) count++;
            return;
        }

        // 현재 전달 받은 index + 1, 현재 전달받은 배열에 현재 인덱스 값 추가해서 함수 호출
        // 전달한 배열의 길이가 3이면 return 되어 i가 더해짐
        for (let i = index; i < nums.length; i++) {
            findCombinations(i + 1, [...selected, nums[i]], sum + nums[i]);
        }
    }

    // 첫 번째 인덱스부터 조합 생성 시작
    findCombinations(0, [], 0);

    return count;
}

재귀를 생각해내기가 어려운 문제인 것 같다.

이해하고 나면 그렇게 어려운 알고리즘은 아니지만, 인적 사고로 바로 생각해내기에는 복잡함이 있다.

또한, 오히려 재귀를 쓰면 시간 초과가 되는 문제들이 있기 때문에 주어진 문제에 맞추어 알고리즘을 잘 선택해야할 것 같다.

​

특히, 프로그래머스의 모음 사전과 같은 문제는 재귀를 사용하기가 더욱 어려운 문제였고,

피보나치 수 문제는 재귀를 사용하면 시간 초과, for문을 사용해야 통과되는 경우가 있었다.