[boj] 9020. 골드바흐의 추측 (node.js)

문제 요약

[boj] 9020. 골드바흐의 추측 (node.js)

• 골드바흐의 추측은 정수론 개념 중 하나로, '2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다.'를 뜻한다.
• 주어진 짝수에 대해 골드바흐의 추측을 만족하는 두 소수를 골드바흐 파티션이라고 할 때, 주어진 수에 대한 골드바흐 파티션을 구하는 문제.

풀이

• 문제에 입력 범위가 제시되어 있으므로, 에라토스테네스의 체를 이용해서 소수를 모두 구한다. 나는 cand[인덱스] == 1 이면 소수 로 배열 인덱스 값을 통해 구분 가능하도록 했다.
• 테스트케이스에 대해 while 문으로 답을 구한다.
  • 주어진 수를 n이라 할 때, n에 대한 골드바흐 파티션이 여러 개일 경우, 두 수의 차가 가장 작은 조합을 출력하므로 인덱스가 n/2 일 때부터 소수 여부를 파악한다.
    • 이때 소수이면 n에서 이 소수를 뺀 숫자도 소수여야 하므로 해당 조건을 만족하면 정답을 구한 것이므로 break
    • 소수가 아니면 값을 중간값에서 더 멀리하여 다시 탐색한다. (문제에 의해 답은 무조건 존재하므로)

내 풀이

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const solution = () => {
  let cand = new Array(10000 + 1).fill(1);
  for (let i = 0; i <= 10000; i++) {
    if (i == 0 || i == 1) {
      cand[i] = 0;
      continue;
    }
    for (let j = 2; i * j <= 10000; j++) {
      if (cand[i * j] == 0) continue;
      cand[i * j] = 0;
    }
  }
  let results = [];
  let T = input();
  for (let i = 0; i < T; i++) {
    let n = Number(input());
    let [a, b] = func(n);
    results.push(a + " " + b);
  }
  console.log(results.join("\n"));

  function func(X) {
    let val;
    let mid = Math.floor(X / 2);
    while (!val) {
      if (cand[mid] && cand[X - mid]) {
        val = Math.min(mid, X - mid);
      } else {
        mid--;
      }
    }
    return [val, X - val];
  }
};

let _line = 0;
const input = () => stdin[_line++];

let stdin = [];
rl.on("line", function (line) {
  stdin.push(line);
}).on("close", function () {
  solution();
  process.exit();
});

주절주절

• 문제 초반에 탐색으로 접근해야겠다는 막연한 생각이 들었고, 아무 생각 없이 손에 익은 이분 탐색을 구현해버렸다. 그런데 다시 꼼꼼히 코드를 살펴보니 그렇게 접근한 덕택에 이분탐색 알고리즘의 뼈대인 while 문 내부에서 값을 효율적으로 탐색하는 로직을 구현할 수 있었다! 덕분에 시간복잡도의 무리 없이 깔끔하게 풀 수 있었던 운 좋은 경험이었다.