[백준] 7795 먹을 것인가 먹힐 것인가 Node.js (이진 탐색 풀이)

문제

심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 수 있는 쌍의 개수는 7가지가 있다. 8-3, 8-6, 8-1, 7-3, 7-6, 7-1, 3-1.

두 생명체 A와 B의 크기가 주어졌을 때, A의 크기가 B보다 큰 쌍이 몇 개나 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 A의 수 N과 B의 수 M이 주어진다. 둘째 줄에는 A의 크기가 모두 주어지며, 셋째 줄에는 B의 크기가 모두 주어진다. 크기는 양의 정수이다. (1 ≤ N, M ≤ 20,000)

출력

각 테스트 케이스마다, A가 B보다 큰 쌍의 개수를 출력한다.

예제 입력 1

2
5 3
8 1 7 3 1
3 6 1
3 4
2 13 7
103 11 290 215

예제 출력 1

7
1

---

문제풀이

✅ 답안 #1

const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const tc = input.shift();

// 각 테스트 케이스에 대한 입력을 처리하기 위한 반복문
for (let i = 0; i < tc; i++) {
  const [sizeA, sizeB] = input.shift().split(' ').map(Number);
  const arrA = input.shift().split(' ').map(Number).sort((a, b) => a - b);
  const arrB = input.shift().split(' ').map(Number).sort((a, b) => a - b);

  let result = 0;
  let bIndex = 0;

  for (const A of arrA) {
	// 배열 A의 현재 원소가 배열 B의 원소보다 크고, bIndex가 배열 B의 길이보다 작은 동안 반복
    while (A > arrB[bIndex] && bIndex < sizeB) {
      bIndex++; // 배열 A의 현재 원소보다 크거나 같은 원소를 찾을 때까지 bIndex를 증가
    }
    result += bIndex; // bIndex에는 배열 A의 현재 원소보다 작은 원소의 개수 저장
  }
  console.log(result);
}

✅ 답안 #2

const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const tc = input.shift();
let result = [];

// 이진 탐색
const binarySearch = (start, end, target, arr) => {
  if (start > end) return start;
  const mid = Math.floor((start + end) / 2);

  // 배열 B의 중간 인덱스의 값이 target(배열 A의 원소)보다 작으면
  if (arr[mid] < target) {
	// 시작 인덱스를 'mid + 1'로 설정 후 재귀
    return binarySearch(mid + 1, end, target, arr);
  } else { // 그렇지 않으면 마지막 인덱스를 'mid - 1'로 설정 후 재귀
    return binarySearch(start, mid - 1, target, arr);
  }
};

// 각 테스트 케이스에 대한 입력을 처리하기 위한 반복문
for (let i = 0; i < tc; i++) {
  const [sizeA, sizeB] = input.shift().split(' ').map(Number);
  const arrA = input.shift().split(' ').map(Number);
  const arrB = input.shift().split(' ').map(Number).sort((a, b) => a - b);

  const startIdx = 0; // 시작 인덱스 0
  const endIdx = sizeB - 1; // 마지막 인덱스는 배열 B의 마지막 인덱스로 설정
  let count = 0; // 탐색 후 결과(개수) 저장할 변수

  // 이진 탐색에 쓰일 target(배열 A의 현재 원소)을 보내기 위한 반복문 
  for (const target of arrA) {
    count += binarySearch(startIdx, endIdx, target, arrB);
  }
  result.push(count); // 탐색 결과를 result 배열에 담기
}

console.log(result.join('\n'));