[백준] 17103번 골드바흐 파티션(Node.js)

김방울·2024년 4월 15일

코딩테스트

목록 보기

2/6

문제

골드바흐의 추측: 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다.
짝수 N을 두 소수의 합으로 나타내는 표현을 골드바흐 파티션이라고 한다. 짝수 N이 주어졌을 때, 골드바흐 파티션의 개수를 구해보자. 두 소수의 순서만 다른 것은 같은 파티션이다.

입력

첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다.

출력

각각의 테스트 케이스마다 골드바흐 파티션의 수를 출력한다.

풀이

처음에 제출했던 풀이(시간초과)

const path = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
const fs = require('fs');
const input = fs
  .readFileSync(path)
  .toString()
  .split('\n')
  .map((el) => parseInt(el));

// 소수 판별 함수
const isPrime = (n) => {
  if (n < 2) return false;
  for (let i = 2; i <= parseInt(Math.sqrt(n)); i++) {
    if (n % i === 0) return false;
  }
  return true;
};

for (let idx = 1; idx < input.length; idx++) {
  let cnt = 0;
  for (let i = 2; i <= input[idx] / 2; i++) {
    // 두 소수의 순서만 다른 것은 같은 파티션이므로, input[idx]의 절반까지만 구한다.
    if (isPrime(i) && isPrime(input[idx] - i)) {
      cnt++;
    }
  }

  console.log(cnt);
}

정답 풀이

const path = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
const fs = require('fs');
const input = fs
  .readFileSync(path)
  .toString()
  .trim()
  .split('\n')
  .map((el) => parseInt(el));
input.shift();

// 소수 판별 함수
const isPrime = (n) => {
  if (n < 2) return false;
  for (let i = 2; i <= parseInt(Math.sqrt(n)); i++) {
    if (n % i === 0) return false;
  }
  return true;
};

const primeArr = Array.from({ length: Math.max(...input) + 1 }); // 0이 포함되어 있음

primeArr[0] = false;
primeArr[1] = false;

for (let i = 2; i < primeArr.length; i++) {
  primeArr[i] = isPrime(i); 
}

for (let idx = 0; idx < input.length; idx++) {
  let cnt = 0;

  for (let i = 2; i <= input[idx] / 2; i++) {
    if (primeArr[i] && primeArr[input[idx] - i]) cnt++;
  }
  console.log(cnt);
}

비교분석

// 정답 풀이
const primeArr = Array.from({ length: Math.max(...input) + 1 }); // 0이 포함되어 있음

primeArr[0] = false;
primeArr[1] = false;

for (let i = 2; i < primeArr.length; i++) {
  primeArr[i] = isPrime(i); // i가 소수인지 판별
}

for (let idx = 0; idx < input.length; idx++) {
  let cnt = 0;

  for (let i = 2; i <= input[idx] / 2; i++) {
    if (primeArr[i] && primeArr[input[idx] - i]) cnt++;
  }
  console.log(cnt);
}

// 시간초과 풀이
for (let idx = 1; idx < input.length; idx++) {
  let cnt = 0;
  for (let i = 2; i <= input[idx] / 2; i++) {
    // 두 소수의 순서만 다른 것은 같은 파티션이므로, input[idx]의 절반까지만 구한다.
    if (isPrime(i) && isPrime(input[idx] - i)) {
      cnt++;
    }
  }
  console.log(cnt);
}

시간초과 풀이의 경우 이중 for문으로 2부터 입력값까지 반복하며 소수 여부를 판별합니다. 이미 소수여부를 한번 판별한 수여도 for문을 돌며 2부터 2부터 입력값 / 2 까지 소수여부를 반복 계산하기 때문에 비효율적입니다. 소수여부 계산식(isPrime) 안에 for문이 있으므로, 시간복잡도는 O(n^3)입니다.

정답 풀이의 경우 먼저 입력값 중 제일 큰 수(Math.max(...input)) 까지의 소수 여부를 전부 판별한 후, 골드바흐 파티션의 갯수 cnt를 출력하는 이중 for문에서는 primeArr 배열에 들어있는 값만 비교하기 때문에 시간복잡도가 O(n^2)가 됩니다.

시간 단축

const path = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
const fs = require('fs');
const input = fs
  .readFileSync(path)
  .toString()
  .trim()
  .split('\n')
  .map((el) => parseInt(el));
input.shift();

const maxNum = Math.max(...input);
const primeArr = Array.from({ length: maxNum + 1 }, () => true); // primeArr에는 0이 포함되어 있으므로, length는 maxNum+1로 설정

primeArr[0] = false;
primeArr[1] = false;

for (let i = 2; i <= parseInt(Math.sqrt(maxNum)); i++) {
  /* N의 약수는 무조건 Math.sqrt(N)의 범위에 존재한다. 
   * 따라서, N까지 for문을 전부 돌릴 필요 없이 Math.sqrt(N) 까지만 수행하고
   * 소수의 배수를 전부 false처리하면 된다.
   */
  if (primeArr[i]) {
    // i가 소수일 경우
    for (let j = 2; j <= maxNum / i; j++) {
      primeArr[i * j] = false; // i의 배수는 전부 소수가 아님
    }
  }
}

for (let idx = 0; idx < input.length; idx++) {
  let cnt = 0;

  for (let i = 2; i <= input[idx] / 2; i++) {
    // 두 소수의 순서만 다른 것은 같은 파티션이므로, input[idx] / 2 까지만 반복
    if (primeArr[i] && primeArr[input[idx] - i]) cnt++;
  }
  console.log(cnt);
}

시간이 오래 걸리는 것 같아 로직을 수정하였더니 실행 시간과 메모리가 유의미하게 줄어들었습니다👀

최대 입력값(maxNum)의 약수는 최대 입력값의 제곱근 내에 있기 때문에, 최대 입력값 제곱근 내 소수를 구한 뒤 소수의 배수들을 지우는 형식으로 구현하면 실행 횟수를 줄일 수 있습니다.

for (let i = 2; i <= parseInt(Math.sqrt(maxNum)); i++)  // 입력값이 100일 경우, 100의 제곱근번 실행
for (let i = 2; i < primeArr.length; i++)  // 입력값이 100일 경우, 99번 실행