백준 1920번 수 찾기 - node.js

해당 포스팅은 백준 1920번 수 찾기 풀이를 다룬다. 문제 링크
코드는 javascript로 작성하였다.

문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

입력

1. [첫째 줄] : N(1 ≤ N ≤ 100,000)
2. [두 번째 줄] : N개의 정수 A[1], A[2], …, A[N]
3. [세 번째 줄] : M(1 ≤ M ≤ 100,000)
4. [네 번째 줄] : M개의 정수가 주어지는 데, 이 수들이 A안에 존재하는지 판별한다.
   → 존재하면 1, 존재하지 않으면 0

• 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

풀이

이 문제는 이분탐색으로 풀어야한다. 그 이유는 N, M이 최대 100000개이므로 시간초과가 날 것이다.

1. 따라서 배열 A(N개의 정수)을 정렬한 다음,
2. 두 번 째 배열(M개의 정수)을 loop돌리면서 배열 A에 해당 el이 존재하는지를 판별한다.
   존재할 시 1을, 존재하지 않을 시 0을 반환한다.

전체 코드

const input = require('fs').readFileSync('/dev/stdin').toString().split('\n');
const [N, sortedList, M, testList] = input.map((el) =>
  el.split(" ").map((val) => +val)
);

sortedList.sort((a, b) => a - b);

// 이분탐색 함수
function binarySearch(arr, elem, start, end, middle) {
  middle = Math.floor((start + end) / 2);
  while (start <= end) {
    if (arr[middle] === elem) return 1;
    if (elem < arr[middle]) end = middle - 1;
    else start = middle + 1;
    middle = Math.floor((start + end) / 2);
  }
  return 0;
}

const result = testList.map((el) => {
  return binarySearch(sortedList, el, 0, sortedList.length - 1, 0);
});
console.log(result.join("\n"));