[boj] 3273. 두 수의 합 (node.js)

문제 요약

[boj] 3273. 두 수의 합 (node.js)

• 수열의 크기와 수열, 숫자 x가 주어진다.
• 서로 다른 두 수의 합이 x가 되는 쌍의 개수를 구하라.

풀이

• 이분 탐색의 조건을 활용해서 수열의 각 원소마다 그 원소와 합했을 때 x가 되는 수를 탐색한다.
• 유의:
  • 이때 탐색 결과가 "쌍의 개수"를 구하는 것이므로 정렬 완료 상태인 배열이므로
  • 탐색 완료한 인덱스가 입력했던 수열 원소의 인덱스보다 작거나 같으면 false를 반환한다.

내 풀이

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

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

let stdin = [];
rl.on("line", function (line) {
  stdin.push(line);
}).on("close", function () {
  const n = input();
  const arr = input().split(" ").map(Number);
  const x = input();
  let cnt = 0;
  arr.sort((a, b) => a - b);
  for (let i = 0; i < n - 1; i++) {
    if (binarySearch(0, n - 1, i)) cnt++;
  }
  console.log(cnt);
  process.exit();

  function binarySearch(L, R, idx) {
    let value = x - arr[idx];
    let result = -1;
    while (L <= R) {
      let mid = Math.trunc((L + R) / 2);
      if (arr[mid] < value) {
        L = mid + 1;
      } else {
        result = mid;
        R = mid - 1;
      }
    }
    if (result <= idx) return false;
    return arr[result] == value;
  }
});