[백준 1920] 이분 탐색 - 수 찾기

✨ 정답 ✨

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

// let n = +input[0].trim();
// 이분탐색을 위해 오름차순으로 정렬해준다.
let findArray = input[1]
  .trim()
  .split(" ")
  .map((el) => +el)
  .sort((a, b) => a - b);
// let m = +input[2].trim();
let targetArray = input[3]
  .trim()
  .split(" ")
  .map((el) => +el)

const binarySearch = (array, target) => {
  let left = 0;
  let right = array.length - 1;
  while (left <= right) {
    let middle = Math.floor((left + right) / 2);
    if (array[middle] === target) {
      return true;
    } else if (array[middle] < target) {
      left = middle + 1;
    } else {
      right = middle - 1;
    }
  }
  return false;
};

let answer=[];
targetArray.map((el) => {
  if (binarySearch(findArray, el)===true) {
    answer.push(1)
  } else {
    answer.push(0)
  }
});

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




// 시간 초과 코드(이분 탐색을 사용하지 않았다)
// const { json } = require("express/lib/response");
// // const fs = require("fs");
// const filePath = process.platform === "linux" ? "/dev/stdin" : "./예제.txt";
// let input = require("fs").readFileSync(filePath).toString().trim().split('\n');

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


// let n=+input[0].trim();
// let findArray=input[1].trim().split(' ').map((el)=>+el)
// let m=+input[2].trim();
// let targetArray=input[3].trim().split(' ').map((el)=>+el)

// for (let target of targetArray){
//   let isThere=false;
//   if (findArray.includes(target)){
//     isThere=true;
//   }
//   if (isThere){
//     console.log(1)
//   }else{
//     console.log(0)
//   }
// }

🧵 참고한 정답지 🧵

💡💡 기억해야 할 점 💡💡

1. 시간 초과가 난 방식의 문제점
   findArray.includes(target)의 includes 메소드는 배열을 처음부터 끝까지 순차적으로 탐색한다. 즉, 시간 복잡도가 O(n)이다. 따라서 이 방법을 사용하면 전체 시간 복잡도는 O(n* m)이 된다. 따라서 입력 크기가 커지면 시간 초과가 발생할 수 있다.

2. 정답(이진 탐색)
   주의점 : 이진 탐색을 사용해도 결과를 출력할 때, console.log를 반복해서 출력하면 안된다.
   한동안 백준을 안 했더니 까먹었었다. answer 배열을 만들고 답을 answer에 다 푸시해두고 join("\n")을 해서 console.log는 한 번만 사용해야 한다.