[백준 1920/javascript] 수 찾기

포함 여부를 파악하는 것뿐이지만, 많은 범위를 제한 시간내에 탐색하기가 힘들다

일반 완전 탐색으로는 10만 * 10만 의 경우의 수이니 시간 초과가 되므로

이진 탐색을 통해 문제를 풀었다

반복문을 사용해도 되지만 재귀함수로 풀어보았다

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

1920번: 수 찾기

let input = [];

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

readline.on("line", (line) => {
  input.push(line);
});

readline.on("close", () => {
  solution(input);
  process.exit();
});

const solution = (input) => {
  let n = Number(input[0]);
  let arr1 = input[1].split(" ").map((el) => Number(el));
  let arr2 = input[3].split(" ").map((el) => Number(el));

  let ans = [];
  arr1.sort((a, b) => a - b);

  const binary = (a, arr, start, end) => {
    let m = Math.floor((start + end) / 2);
    if (start > end) {
      return 0;
    }
    if (a === arr[m]) {
      return 1;
    }
    if (a < arr[m]) {
      return binary(a, arr, start, m - 1);
    } else {
      return binary(a, arr, m + 1, end);
    }
  };

  for (el of arr2) {
    ans.push(binary(el, arr1, 0, arr1.length - 1));
  }
  console.log(ans.join("\n"));
};