JavaScript 코딩테스트 - lower_bound, upper_bound

코딩 테스트 대비 저장용 포스트입니다.

C++에는 algorithm 으로 해당 기능을 지원했는데 없어서 구현해보았다.

BOJ 10816번: 숫자 카드 2 문제

• upper_bound - lower_bound로 그 수의 개수를 계산했다. (이 문제는 다른 방법이 더 쉽긴 하다.)

"use strict";

// target 보다 큰 가장 왼쪽 원소 찾기
const upperBound = (arr, target) => {
  let le = 0,
    ri = arr.length;
  while (le < ri) {
    const mid = Math.floor((le + ri) / 2);
    if (target < arr[mid]) {
      ri = mid;
    } else {
      le = mid + 1;
    }
  }
  return ri;
};

// target 보다 작거나 같은 가장 왼쪽 인덱스 찾기
const lowerBound = (arr, target) => {
  let le = 0,
    ri = arr.length;
  while (le < ri) {
    const mid = Math.floor((le + ri) / 2);
    if (target <= arr[mid]) {
      ri = mid;
    } else {
      le = mid + 1;
    }
  }
  return ri;
};

const [n, c, m, q] = require("fs").readFileSync("/dev/stdin").toString().split("\n");
const N = Number(n);
const cards = c
  .split(" ")
  .map(Number)
  .sort((a, b) => a - b);
const M = Number(m);
const quizs = q.split(" ").map(Number);

console.log(quizs.map((i) => upperBound(cards, i) - lowerBound(cards, i)).join(" "));