문제

https://www.acmicpc.net/submit/1920/84633322

1차 시도 - 시간초과

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

function run(inputs) {
  const arr1 = inputs[1].split(' ').map(Number);
  const arr2 = inputs[3].split(' ').map(Number);
  const result = [];

  for (const number of arr2) {
    if (arr1.includes(number)) result.push(1);
    else result.push(0);
  }

  return result.join('\\n');
}

console.log(run(inputs))

• arr2를 순회(O(n))하면서 각 요소에 대해 includes를 실행(O(m)) 하기 때문에 시간복잡도는 O(n*m)이다.

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) return true;
    if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return false;
}

function run(inputs) {
  const arr1 = inputs[1]
    .split(' ')
    .map(Number)
    .sort((a, b) => a - b);
  const arr2 = inputs[3].split(' ').map(Number);
  const result = [];

  for (const number of arr2) {
    if (binarySearch(arr1, number)) result.push(1);
    else result.push(0);
  }

  return result.join('\\n');
}

• 선형탐색을 줄이기 위해 이분 탐색이 가능한 자료구조로 변경한다.
• arr1을 정렬하여 이분 탐색한다.
• 이분 탐색 로직의 시간복잡도 O(m log n)
• sort 함수의 시간복잡도 O(n log n)
• 총 시간 복잡도 O(n log n + m log n)