[boj] 7795. 먹을 것인가 먹힐 것인가 (node.js)

문제 요약

1. 입력: A, B 집합을 구성하는 각각의 원소들이 주어질 때
2. 조건: A가 B보다 큰
3. 출력: (A, B) 원소의 조합의 개수를 출력

풀이

접근

B보다 큰 A의 원소의 개수를 for문을 돌면서 세면 된다. 이때 B배열을 정렬 완료된 상태에서 A의 각각의 원소에 대해 이분탐색한다.
탐색 알고리즘 내부에서는 그 값보다 작은 원소의 개수를 인덱스를 활용해 반환할 수 있다. 이를 모두 합치면 각 테스트케이스에 대한 조합의 개수가 된다.

내 코드

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let stdin = [];
let cnt = 0;
const input = () => {
  return stdin[cnt++];
};

const binarySearch = (arr, L, R, elem) => {
  let result = L,
    mid;
  while (L <= R) {
    mid = Math.trunc((L + R) / 2);
    if (arr[mid] < elem) {
      result = mid + 1;
      L = mid + 1;
    } else {
      R = mid - 1;
    }
  }
  return result;
};

rl.on("line", (line) => {
  stdin.push(line);
}).on("close", () => {
  let T = input();
  while (T--) {
    const [N, M] = input().split(" ").map(Number);
    const A = input().split(" ").map(Number);
    const B = input().split(" ").map(Number);
    B.sort((a, b) => a - b);
    console.log(
      A.reduce((sum, elem) => {
        const result = binarySearch(B, 0, M - 1, elem);
        return sum + result;
      }, 0)
    );
  }
  process.exit();
});

기억할 것들

1. 이분 탐색 알고리즘 외부: 매개변수로 줄 인덱스 값 확인하기!
   이번에는 (배열, L인덱스, R인덱스, 확인할 원소)를 매개변수로 코드를 짰다. 초기값을 제대로 확인하고 넣지 않으면 사소한 오류로 값이 나오지 않을 수 있다.
2. 이분 탐색 알고리즘 내부: 문제의 요구조건에 따라 반환한 result의 초기값과 재할당 값 확인하기!
   이 문제의 경우는 L의 인덱싱이 0부터 들어가게 구현했으므로, result값이 갱신될 때 result = mid;로 대입시 개수를 잘못 세게 된다. result = mid + 1;을 해야만 문제에서 요하는 답을 반환할 수 있다.

주절주절

1. node.js 쓸 때는 최대한 readline 모듈만 사용해서 풀어야겠다. 깔끔하고 빠르게 돌아가니까 기분이 좋다!
2. 배열 함수를 이렇게 써본 경험이 적은데, reduce 함수 너무 편리하고 좋다. 써볼수록 참 신기하고 재밌다!