코테15 - 소수만들기

기존코드의 문제

function solution(nums) {
    var answer = 0;
    
    function isPrime(num) {
	    if(num === 1) return false; 
        // Math.sqrt 함수를 사용하여 제곱근까지만 반복하도록 한다.
        for(let i = 2; i <= parseInt(Math.sqrt(num)); i++) {
            if(num % i === 0) return false;
        } 
        return true; 
    }
    
    let arr = [];
    nums.forEach((e) => {
        nums.forEach((a) => {
            if(e !== a){
                nums.forEach((x) => {
                    if(x !== a && x !== e){
                        arr.push(e + a + x);
                    }
                })
            }
        })
    })
    const set = new Set(arr)

    Array.from(set).forEach((e) => {
        const prime = isPrime(e);
        if(prime) answer++
    })
        
    return answer;
}

 

문제의 핵심은 주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 찾는 것입니다. 주어진 코드에는 몇 가지 문제가 있습니다.

1. 중복된 조합 처리: 현재 코드는 중복된 조합을 처리하지 않고 있습니다. 예를 들어, 1, 2, 3과 3, 2, 1을 같은 조합으로 처리하지 않습니다.
2. 효율성: 중복된 계산이 너무 많습니다.

이 문제를 해결하기 위해 다음과 같은 접근 방식을 사용할 수 있습니다:

• 3중 for 루프를 사용하여 nums 배열에서 3개의 숫자를 선택합니다.
• 선택된 3개의 숫자를 더한 후, 그 합이 소수인지 체크합니다.
• 소수인 경우 카운터를 증가시킵니다.

이제 이를 코드로 구현해보겠습니다.

function solution(nums) {
    var answer = 0;

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

    let n = nums.length;

    // 3중 for 루프를 사용하여 모든 3개의 숫자 조합을 확인합니다.
    for (let i = 0; i < n - 2; i++) {
        for (let j = i + 1; j < n - 1; j++) {
            for (let k = j + 1; k < n; k++) {
                let sum = nums[i] + nums[j] + nums[k];
                if (isPrime(sum)) {
                    answer++;
                }
            }
        }
    }

    return answer;
}

// 테스트 케이스
console.log(solution([1, 2, 3, 4])); // 1
console.log(solution([1, 2, 7, 6, 4])); // 4

이 코드는:

1. isPrime 함수는 주어진 수가 소수인지 확인합니다.
2. 3중 for 루프를 통해 nums 배열의 모든 3개 숫자 조합을 검사합니다.
3. 각 조합의 합이 소수인지 확인하고, 소수일 경우 카운터를 증가시킵니다.

이렇게 하면 중복된 조합 없이 모든 가능한 조합을 검사할 수 있고, 효율적으로 문제를 해결할 수 있습니다.

 

 

길이 - 2, -1 하는 이유?

nums.length - 2와 nums.length - 1의 사용 이유는 3중 for 문을 통해 모든 가능한 3개의 숫자 조합을 효율적으로 탐색하기 위함입니다. 이를 좀 더 구체적으로 설명해드리겠습니다:

1. i의 범위 (0부터 n-2까지):
   • 첫 번째 for 문에서 i는 0부터 n-2까지 반복합니다.
   • 이는 i를 선택했을 때, 최소한 두 개의 숫자가 남아있어야 하기 때문입니다. 만약 i가 n-2보다 크면, 두 개의 숫자를 선택할 수 없게 됩니다.
2. j의 범위 (i+1부터 n-1까지):
   • 두 번째 for 문에서 j는 i+1부터 n-1까지 반복합니다.
   • 이는 j를 선택했을 때, 최소한 한 개의 숫자가 남아있어야 하기 때문입니다. 만약 j가 n-1보다 크면, 하나의 숫자를 선택할 수 없게 됩니다.
   • 또한, j는 항상 i보다 뒤에 있는 숫자를 선택해야 중복을 피할 수 있습니다.
3. k의 범위 (j+1부터 n까지):
   • 세 번째 for 문에서 k는 j+1부터 n까지 반복합니다.
   • 이는 k가 항상 i와 j보다 뒤에 있는 숫자를 선택하게 하여 중복을 피하고, 마지막 숫자를 선택하기 위함입니다.

예를 들어, nums 배열의 길이가 5라면:

• i는 0부터 3까지 반복합니다 (n-2).
• j는 i+1부터 4까지 반복합니다 (n-1).
• k는 j+1부터 5까지 반복합니다 (n).

이를 통해 모든 가능한 3개의 숫자 조합을 탐색할 수 있습니다. 다음은 예제를 통해 살펴보겠습니다:

nums = [1, 2, 3, 4, 5]

// i = 0, j = 1, k = 2
// i = 0, j = 1, k = 3
// i = 0, j = 1, k = 4
// i = 0, j = 2, k = 3
// i = 0, j = 2, k = 4
// i = 0, j = 3, k = 4
// i = 1, j = 2, k = 3
// i = 1, j = 2, k = 4
// i = 1, j = 3, k = 4
// i = 2, j = 3, k = 4

모든 가능한 3개의 숫자 조합을 탐색하는 동안, 각 조합의 합이 소수인지 확인하고 소수인 경우 카운터를 증가시킵니다.

다시 한번 전체 코드를 정리하면 다음과 같습니다:

function solution(nums) {
    var answer = 0;

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

    let n = nums.length;

    // 3중 for 루프를 사용하여 모든 3개의 숫자 조합을 확인합니다.
    for (let i = 0; i < n - 2; i++) {
        for (let j = i + 1; j < n - 1; j++) {
            for (let k = j + 1; k < n; k++) {
                let sum = nums[i] + nums[j] + nums[k];
                if (isPrime(sum)) {
                    answer++;
                }
            }
        }
    }

    return answer;
}

// 테스트 케이스
console.log(solution([1, 2, 3, 4])); // 1
console.log(solution([1, 2, 7, 6, 4])); // 4

이 코드는 주어진 숫자 배열에서 가능한 모든 3개의 숫자 조합을 찾아 합이 소수인 경우를 정확하게 셉니다.