[백준 1920번] 수 찾기 - 자바스크립트(nodejs)

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

1920번: 수 찾기

const fs = require('fs');
const input = fs.readFileSync('dev/stdin').toString().trim().split('\n');

const binarySearch = (arr, num) => {
  let start = 0;
  let end = arr.length - 1;

  while (start <= end) {
    let middle = Math.floor((start + end) / 2);
    if (arr[middle] < num) {
      start = middle + 1;
    } else if (arr[middle] > num) {
      end = middle - 1;
    } else {
      return 1;
    }
  }
  return 0;
};

const haveCard = input[1]
  .split(' ')
  .sort((a, b) => a - b)
  .map(Number);

const isCard = input[3].split(' ').map(Number);

const answer = isCard.map((v) => {
  return binarySearch(haveCard, v);
});

console.log(answer.join('\n'));

아주 쉬운 로직이지만, 이분 탐색을 구현하지 않으면 시간초과로 풀리지 않는다.

O(N) 복잡도가 아닌 O(logN)인 이분 탐색으로 구현하면 빠르게 작동해 풀 수 있다.