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

문제 링크

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

풀이 과정

const SIZE = 3000;
let sosu = Array(SIZE).fill(true);
let answer = 0;
sosu[0] = sosu[1] = false;

for (let i = 2; i * i < SIZE; i++) {
    if (!sosu[i]) continue;

    for (let j = i * i; j < SIZE; j += i) {
        sosu[j] = false;
    }
}

먼저 에라토스테네스의 체를 활용하여 소수를 구분해 놓습니다.

• 배열 nums 에서 세 개의 숫자를 골라 더할 것이고, nums 에는 최대 1000 이하의 값이 들어있으므로, 배열 sosu 의 최대 크기를 3000 으로 설정했습니다.
• 배열 sosu 는, 각 인덱스로 설정된 숫자가 소수인지를 저장하는 배열입니다. fill(true) 를 통해, 모든 수가 소수라고 초기화 해둡니다.
• 0과 1은 소수가 아니므로, false 로 설정해 두고, for 문을 통해 나머지 수들을 소수 체크합니다.

for (let i = 0; i < nums.length - 2; i++) {
    for (let j = i + 1; j < nums.length - 1; j++) {
        for (let k = j + 1; k < nums.length; k++) {
            let sum = nums[i] + nums[j] + nums[k];

            if (!sosu[sum]) answer++;
        }
    }
}

반드시 3 개를 고르므로, 굳이 조합 함수를 구현해서 적용할 필요가 없습니다. 3중 for 문을 통해, 각각의 인덱스를 하나의 수로 매칭해서 숫자 세 개를 고릅니다.

코드

function solution(nums) {
    const SIZE = 3000;
    let sosu = Array(SIZE).fill(false);
    let answer = 0;
    sosu[0] = sosu[1] = true;

    for (let i = 2; i * i < SIZE; i++) {
        if (sosu[i]) continue;

        for (let j = i * i; j < SIZE; j += i) {
            sosu[j] = true;
        }
    }

    for (let i = 0; i < nums.length - 2; i++) {
        for (let j = i + 1; j < nums.length - 1; j++) {
            for (let k = j + 1; k < nums.length; k++) {
                let sum = nums[i] + nums[j] + nums[k];

                if (!sosu[sum]) answer++;
            }
        }
    }

    return answer;
}

solution([1, 2, 3, 4]);
solution([1, 2, 7, 6, 4]);