[BOJ 11663 🥈3] 선분 위의 점 (JavaScript)

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

 

문제

일차원 좌표상의 점 N개와 선분 M개가 주어진다. 이때, 각각의 선분 위에 입력으로 주어진 점이 몇 개 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 점의 개수 N과 선분의 개수 M이 주어진다. (1 ≤ N, M ≤ 100,000) 둘째 줄에는 점의 좌표가 주어진다. 두 점이 같은 좌표를 가지는 경우는 없다. 셋째 줄부터 M개의 줄에는 선분의 시작점과 끝점이 주어진다. 입력으로 주어지는 모든 좌표는 1,000,000,000보다 작거나 같은 자연수이다.

출력

입력으로 주어진 각각의 선분 마다, 선분 위에 입력으로 주어진 점이 몇 개 있는지 출력한다.

예제 입력 1

5 5
1 3 10 20 30
1 10
20 60
3 30
2 15
4 8

예제 출력 1 

3
2
4
2
0

 

⭕ CODE

const fs = require("fs");
const input =
  process.platform === "linux"
    ? fs.readFileSync("/dev/stdin").toString().split("\n")
    : fs.readFileSync("example.txt").toString().split("\r\n");

const [n, m] = input[0].split(" ").map((v) => parseInt(v));

const bisectLeft = (arr,value) => {
  let left = 0;
  let right = n;

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

const bisectRight = (arr,value) => {
  let left = 0;
  let right = n;

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

const arr = input[1].split(" ").map((v) => parseInt(v));


arr.sort((a,b) =>( a - b));

const result = new Array();
for (let i = 2; i < m+2; i++) {
  const [s,e] = input[i].split(" ").map((v) => parseInt(v));
  answer = bisectRight(arr,e) - bisectLeft(arr,s)
  result.push(answer)
}
console.log(result.join('\n'))

✏️ Comment

문제를 확인하고 각각의 좌표가 어느 지점(index)에 들어가는지 확인하여 그 사이에 있는 개수를 파악하려고 하였다. 

1 3 10 20 30 에서 1 10을 예시로 들면 1과 10은 포함하므로 2가지가 된다. 이 말은 즉 시작지점은 포함하면 왼쪽 인덱스(bisect_left)위치에 존재하고 끝지점은 포함한다면 오른쪽 인덱스(bisect_right)위치에 존재해야한다.

• 문제 해결 방안은 금방 생각하였으나 JavaScript로 문제를 처음 풀어서 많이 어려웠다.