알고리즘 기초 1/2. 301 - 수학 1(연습)
17103번. 골드바흐 파티션

문제

17103번 문제 링크

solution

const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n").map((item) => Number(item));

const iter = input.shift();

// 모든 경우에서 소수를 찾기보다는
// 주어진 경우 중 가장 큰 수까지의 소수까지만 구한 뒤
// 활용하는게 좋아보임
let maxNum = Math.max(...input);

let ans = "";

// maxNum까지의 소수 구하기
let prime = new Array(maxNum + 1).fill(true);
prime[0] = false;
prime[1] = false;

for(let i = 2; i <= (maxNum / 2); i++){
    if(prime[i]){
        for(let j = 2; j <= (maxNum / i); j++){
            prime[i * j] = false;
        }
    }
}

// 골드바흐 파티션
input.forEach((item) => { 
    // 각 케이스에 대한 정답 개수를 측정하기 위함.
    let count = 0;
    
    for(let i = 2; i <= (item / 2); i++){        
        if(prime[i] && prime[item - i]){
            count++;
        }
    }
    
    ans += `${count}\n`;
})

console.log(ans);

가장 큰 변화는 new Array()를 사용해서 소수를 판별할 배열을 만들었다는 것이다.
물론, 이 부분이 시간 초과를 해결한 것은 아니고 그 아래 for문이 해결한 것이다.
이 부분은 소수 판별 때 유용하게 써먹을 것 같으니 잘 알아둬야겠다.

그리고 골드바흐 문제는 두 개의 소수로만 합을 표현하는데, 그렇다보니 가장 작은 소수와 가장 큰 소수부터 해서 점점 좁혀오는 방법을 사용할 수 밖에 없다.
count++ 연산이 진행되는 부분의 반복문, 조건문이 이를 표현한 것이다.
추가적으로 예시 입력 데이터에서 6을 보면 3 + 3으로 표현되어, 같은 소수여도 포함될 수 있다는 점을 알았으므로, i를 item/2까지 포함해서 범위를 지정해주었다.

저번 골드바흐 문제에서는 이런 식으로 안 풀어봐서 방법을 못 찾고, 시간 제한을 해결 못 한 것이 아쉽다.

시간 초과

const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n").map((item) => Number(item));

const iter = input.shift();

// 모든 경우에서 소수를 찾기보다는
// 주어진 경우 중 가장 큰 수까지의 소수까지만 구한 뒤
// 활용하는게 좋아보임
let maxNum = Math.max(...input);

let prime = [];

let ans = "";

// maxNum까지의 소수 구하기
outer:for(let i = 2; i < maxNum; i++){
    inner:for(let j = 2; j*j <= i; j++){
        if(i % j === 0){
            continue outer;
        }
    }
    
    prime.push(i);
}

// 골드바흐 파티션
for(let i = 0; i < input.length; i++){
    let even = input[i];
    
    // 각 케이스에 대한 정답 개수를 측정하기 위함.
    let count = 0;
    
    // prime 배열에서 even보다 작은 소수만 사용할 수 있도록 조정
    // even보다 작은 것만 남겨서 newPrime 배열을 만든다.
    let newPrime = prime.filter((item) => item < even);
    
    for(let j = 0; j < newPrime.length; j++){
        let pivot = newPrime[j];
        
        // 만약 두 개의 소수 합으로 표현이 된다면 count 증가
        // 단, 두 개의 소수는 같은 값이어도 가능하기 때문에, j부터 반복 시작.
        // 두 소수의 순서만 다른 것이라면 같은 결과로 간주하기 때문이기도 하다.
        // 8을 표현할 때, [2,3,5,7]이 있다면, (3,5)와 (5,3)은 같으므로
        // 뒤에 올 숫자를 j부터로 하면 (3,5) 이후에 (5,3)이 나오지 않는다.
        for(let k = j; k < newPrime.length; k++){
            let changedPrime = newPrime[k];
            
            // 두 개의 소수 합으로 even이 표현된다면 count 증가
            if(even === pivot + changedPrime){
                count++;
            }
        }
    }
    
    ans += `${count}\n`;
}

console.log(ans);

for문을 과하게 사용한 것이 문제일까싶어서 forEach로 바꿔보았다.

for -> forEach. 시간 초과

const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n").map((item) => Number(item));

const iter = input.shift();

// 모든 경우에서 소수를 찾기보다는
// 주어진 경우 중 가장 큰 수까지의 소수까지만 구한 뒤
// 활용하는게 좋아보임
let maxNum = Math.max(...input);

let prime = [];

let ans = "";

// maxNum까지의 소수 구하기
outer:for(let i = 2; i < maxNum; i++){
    inner:for(let j = 2; j*j <= i; j++){
        if(i % j === 0){
            continue outer;
        }
    }
    
    prime.push(i);
}

// 골드바흐 파티션
input.forEach((item) => {
    let even = item;
    
    // 각 케이스에 대한 정답 개수를 측정하기 위함.
    let count = 0;
    
    // prime 배열에서 even보다 작은 소수만 사용할 수 있도록 조정
    // even보다 작은 것만 남겨서 newPrime 배열을 만든다.
    let newPrime = prime.filter((num) => num < even);
    
    newPrime.forEach((newItem) => {
        // 만약 두 개의 소수 합으로 표현이 된다면 count 증가
        // 단, 두 개의 소수는 같은 값이어도 가능하기 때문에, j부터 반복 시작.
        // 두 소수의 순서만 다른 것이라면 같은 결과로 간주하기 때문이기도 하다.
        // 8을 표현할 때, [2,3,5,7]이 있다면, (3,5)와 (5,3)은 같으므로
        // 뒤에 올 숫자를 j부터로 하면 (3,5) 이후에 (5,3)이 나오지 않는다.
        for(let i = newItem; i < newPrime.length; i++){
            // 두 개의 소수 합으로 even이 표현된다면 count 증가
            if(even === newItem + newPrime[i]){
                count++;
            }
        }
    })
    
    ans += `${count}\n`;
})

console.log(ans);

두 개의 for문을 forEach로 바꿔보았다. 역시나 해결되지 못했다.
후에 알고보니 for가 forEach보다 1.4배 빠르다고한다;;
그렇다면 문제는 for나 forEach가 아니라,
소수 값들의 배열인 prime 배열의 생성이나 newPrime 배열의 생성에서 발생했을 것이라고 생각된다.

참고 자료

참고 자료 1
참고 자료 2