[백준][이진 탐색] 7795 먹을 것인가 먹힐 것인가 NodeJs 구현

목차

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

문제

 

문제 구현 방향

각각의 생명체는 다르므로 set으로 중복을 제거할 필요는 없다.

한 쪽 값만 결정해 준 뒤에 이진 탐색으로 나머지 값을 차례로 찾으면 된다.

이때 정렬을 하고 해야 쌍의 범위를 결정할 수 있다.

 

 

코드 구현 시 주의점

분기 조건에서 인덱스를 갱신해 주어야 한다. 모든 탐색이 끝난 후의 mid 값으로 값을 결정하면 틀린다. 주의하자

 

 

코드 구현

const input = require("fs")
  .readFileSync("./dev/stdin", "utf-8")
  .trim()
  .split("\n");

let T = +input[0];
input.splice(0, 1);

function binarySearch(arr, brr) {
  let ans = 0;
  arr.sort((a, b) => a - b);
  brr.sort((a, b) => a - b);
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] <= brr[0]) continue;
    let low = 0;
    let high = brr.length - 1;
    let cnt =0;
    while (low <= high) {
      let mid = Math.floor((low + high) / 2);
      if (brr[mid] < arr[i]) {
        low = mid + 1;
        cnt = mid + 1;
      } else {
        high = mid - 1;
      }
    }
    ans += cnt;
  }
  console.log(ans);
}

for (let i = 0; i < T; i++) {
  input.splice(0, 1);
  let a = input[0].trim().split(" ").map(Number);
  input.splice(0, 1);
  let b = input[0].trim().split(" ").map(Number);
  input.splice(0, 1);
  binarySearch(a, b);
}