백준 10816번 숫자 카드 2 JavaScript 풀이 [이진 탐색]

백준 10816번 숫자 카드 2 문제를 자바스크립트로 이진 탐색 알고리즘을 이용해서 풀어보았다. 

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

 

1) 이진 탐색 안쓰고 단순 구현 -> 이 코드도 통과됨

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

// 가지고 있는 숫자 카드 N개
let n = Number(input[0]);
let have = input[1].split(' ').map(Number);

// 비교할 숫자 카드 M개
let m = Number(input[2]);
let stand = input[3].split(' ').map(Number);

let countMap = new Map();

for (let num of have) {
  if (countMap.has(num)) countMap.set(num, countMap.get(num) + 1);
  else countMap.set(num, 1)
}

let answer = stand.map((v) => (countMap.has(v) ? countMap.get(v) : 0))
console.log(answer.join(' '))

 

2) 이진 탐색 사용 -> 통과

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

// 가지고 있는 숫자 카드 N개
let n = Number(input[0]);
let data = input[1].split(' ').map(Number);
data.sort((a, b) => a - b)

// 비교할 숫자 카드 M개
let m = Number(input[2]);
let query = input[3].split(' ').map(Number);

function lowerBound(arr, target, start, end) {
  while (start < end) {
    let mid = parseInt((start + end) / 2);
    if (arr[mid] >= target) end = mid;
    else start = mid + 1;
  }
  return end;
}

function upperBound(arr, target, start, end) {
  while (start < end) {
    let mid = parseInt((start + end) / 2);
    if (arr[mid] > target) end = mid;
    else start = mid + 1;
  }
  return end;
}

function countByRange(arr, leftValue, rightValue) {
  let rightIndex = upperBound(arr, rightValue, 0, arr.length);
  let leftIndex = lowerBound(arr, leftValue, 0, arr.length);
  return rightIndex - leftIndex
};

let answer = "";
for (let i=0; i<m; i++) {
  answer += countByRange(data, query[i], query[i]) + ' ';
}
console.log(answer)