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

프로그래머스 1단계 문제인 '소수 만들기'를 자바스크립트로 풀어보았다.

 

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

 

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

function combination(idx, chosen, nums, sums) {
    if (chosen.length === 3) {
        sums.push(chosen.reduce((acc, cur) => acc + cur, 0));
        return;
    }
    if (idx === nums.length)
        return;
    combination(idx+1, chosen, nums, sums);
    chosen = [...chosen, nums[idx]];
    combination(idx+1, chosen, nums, sums);
}

function solution(nums) {
    let sums = [];
    combination(0, [], nums, sums);
    return sums.filter(n => isPrime(n)).length;
}

 

주어진 수가 소수인지 판단하는 함수, nums 배열에서 3개 원소를 뽑는 모든 경우의 수(조합)를 구하는 함수를 만들었다.

isPrime 함수는 코드를 읽으면 바로 이해할 수 있을 것이다.

combination 함수는 nums 배열을 처음부터 끝까지 훑으며 원소마다 넣고/안 넣고 두 가지 경우를 분기해 재귀시켰다.

combination 함수 알고리즘

 

combination 함수를 짤 때 객체의 얕은 복사, 깊은 복사를 잘못 사용해서 오류가 발생했다.

chosen 배열에 새 원소를 넣어주는 부분을 push를 사용했던 것이다.

이렇게 하면 식별자 chosen이 가리키는 배열을 직접 수정하고, 재귀로 넘겨주는 chosen은 이 식별자와 동일하므로, 재귀로 분기되는 모든 경우의 chosen에 새 원소가 추가된다. (얕은 복사)

아래처럼 spread 문법을 사용하여 chosen에 재할당해주면 새로운 메모리가 할당되어 식별자 chosen이 가리키던 reference가 달라지므로 원하는 대로 작동하게 된다. (깊은 복사)

// X
chosen.push(nums[idx]);
// O
chosen = [...chosen, nums[idx]];

 

또한 sums를 Set을 사용해 오류가 발생했다.

문제에서는 'nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수'를 구하라고 명시되어 있다.

예를 들어 1, 2, 3, 4, 5, 6, 7가 주어질 경우, 소수 11이 되는 [1, 3, 7]의 경우와 [1, 4, 6]의 경우는 서로 다르므로 두 경우 모두 카운트되어야 한다.

문제를 꼼꼼히 읽지 않고, 중복을 제거한다고 생각해서 Set을 사용해서 틀렸다. Array로 변경하니 최종적으로 통과되었다.

문제를 잘 읽자.