[백준 10816번] 숫자 카드2 - 자바스크립트(nodejs)

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

10816번: 숫자 카드 2

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

const binarySearch = (arr, num) => {
  let start = 0;
  let end = arr.length - 1;

  while (start <= end) {
    let middle = Math.floor((start + end) / 2);
    if (arr[middle][0] < num) {
      start = middle + 1;
    } else if (arr[middle][0] > num) {
      end = middle - 1;
    } else {
      return arr[middle][1];
    }
  }
  return 0;
};

const haveCard = input[1]
  .split(' ')
  .sort((a, b) => a - b)
  .map(Number);

const isCard = input[3].split(' ').map(Number);

const arr = [[haveCard[0], 1]];

for (let i = 1; i < haveCard.length; i++) {
  if (haveCard[i - 1] === haveCard[i]) {
    arr[arr.length - 1][1]++;
  } else {
    arr.push([haveCard[i], 1]);
  }
}
const answer = isCard.map((v) => {
  return binarySearch(arr, v);
});

console.log(answer.join(' '));

binarySearch => 이분 탐색 함수

먼저 가지고 있는 숫자 카드 배열을 작은 순서대로 정렬하고, 중복된 카드 개수를 센다.

그 후 binarySearch를 이용해 logN 시간복잡도로 빠르게 구해주면 끝!

그냥 반복문으로 구하면 시간초과가 걸릴 것이다.