[백준 nodeJS] 10815 숫자 카드(이분탐색)

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다

출력

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 가지고 있으면 1을, 아니면 0을 공백으로 구분해 출력한다.

1. 시간 초과 코드

내장 메서드만으로 풀었다가 시간초과가 나오길래 다시 확인했더니 이분 탐색으로 풀었어야 한다.

    const input = require("fs").readFileSync("example.txt").toString().trim();
    const [n, cards, m, numbers] = input.split("\n");
    const cardsArr = cards.split(" ").map(Number);
    const numbersArr = numbers.split(" ").map(Number);
    const result = numbersArr.map((item) => {
      if (cardsArr.includes(item)) return 1;
      return 0;
    });
console.log(result.join(" "));

2. 이분탐색

    const input = require("fs").readFileSync("example.txt").toString().trim();
    const [n, cards, m, numbers] = input.split("\n");
    const cardsArr = cards
      .split(" ")
      .map(Number)
      .sort((a, b) => a - b);
    const numbersArr = numbers.split(" ").map(Number);
    const result = numbersArr.map((item) => binarySearch(cardsArr, item));

    function binarySearch(array, target) {
      let leftEndOfArray = 0;
      let rightEndOfArray = array.length - 1;
      let middle = Math.floor(
        (rightEndOfArray - leftEndOfArray) / 2 + leftEndOfArray
      );
      //middle에 Math.floor를 하든 ceil을 하든 중요하지 않다. 중요한 것은 반복문에 등호가 있어야 한다는 것.
      //등호 없으면 left, middle, right 모두 0일 때 반복문이 작동하지 않아서 0이 반환된다.
      while (leftEndOfArray <= rightEndOfArray) {
        if (array[middle] === target) {
          return 1;
        } else if (array[middle] > target) {
          rightEndOfArray = middle - 1;
        } else if (array[middle] < target) {
          leftEndOfArray = middle + 1;
        }
        middle = Math.ceil((rightEndOfArray - leftEndOfArray) / 2 + leftEndOfArray);
      }
      return 0;
    }
console.log(result.join(" "));