백준1253 - 좋다 (이분탐색) node.js

https://www.acmicpc.net/problem/1253

해당 문제는 원소의 갯수와 원소가 주어질 때, 두 가지 원소의 합이 배열 내 원소 중 하나와 일치하는 경우가 몇 가지인지 출력하는 문제다.

최대로 등장할 수 있는 원소의 갯수가 2천 개이기 때문에, 이분탐색으로 접근했다.

 

문제 풀이 방식은 다음과 같다.

문제에서 주어진 수가 정렬되어 있다는 얘기가 없으므로 이분탐색을 위해 오름차순으로 정렬했다.

이후 배열 내 원소 중 하나인 n을 미리 선택한 뒤,

이분탐색으로 두 가지 수를 합쳤을 경우 n을 만족하는지를 파악하는 방식으로 로직을 구현했다.

const fs = require("fs");
const input = fs
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "입력.txt")
  .toString()
  .trim()
  .split("\n");

function solution(data) {
  const n = +data[0];
  const arr = data[1]
    .split(" ")
    .map(Number)
    .sort((a, b) => a - b);

  const binarySearch = (k) => {
    const list = [...arr.slice(0, k), ...arr.slice(k + 1)];

    let [left, right] = [0, n - 1];
    while (left < right) {
      const mid = list[left] + list[right];
      if (mid === arr[k]) return 1;
      arr[k] > mid ? left++ : right--;
    }
    return 0;
  };

  let result = 0;
  for (let i = 0; i < n; i++) {
    result += binarySearch(i);
  }

  console.log(result);
}

solution(input);