[백준] 10816번 숫자 카드2(JavaScript)

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

1. 객체 방법

let input = require('fs')
  .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
  .toString()
  .trim()
  .split('\n')
  .map((el) => el.split(' ').map(Number));

let N = input.shift()[0];
let first = input.shift().sort((a, b) => a - b);
let M = input.shift()[0];
let second = input.shift();

let classFirst = first.reduce((acc, cur) => {
  acc[cur] = (acc[cur] || 0) + 1;
  return acc;
}, {});

let answer = second.map((el) => {
  return classFirst[el] ? classFirst[el] : 0;
});
console.log(answer.join(' '));

10815번 문제와 내용은 동일하지만 출력을 값의 존재가 아닌 값의 개수로 나타내는 것이다.

방법에는 여러 가지가 있는데 10815에서는 이진 정렬을 사용했지만 10816에서는 이진 배열 방법을 사용하지 않았다.(이진 배열 방법은 밑에 있습니다.)

이번에 사용한 방법은 reduce를 통해 첫 번째 숫자 카드를 객체로 만들어 개수를 저장해 놓은 다음 두 번째 숫자카드가 존재하면 개수 출력 아니면 0을 출력하는 방법을 썼다. 

하지만 원래 문제 의도대로라면 이진 정렬을 사용하는 것이지만 조금 복잡해진다. 그 이유는 sort를 한 다음 숫자를 찾을 때 중복되는 숫자의 경우는 start와 end index부분을 다시 찾아 줘야 한다(ex. -1 -1 0 1 2 2 3의 경우 -1을 발견하면 start를 다시 찾아줘야 한다.)

2. 이진 배열 방법

let input = require('fs')
  .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
  .toString()
  .trim()
  .split('\n')
  .map((el) => el.split(' ').map(Number));

let N = input.shift()[0];
let first = input.shift().sort((a, b) => a - b);
let M = input.shift()[0];
let second = input.shift();
let answer = [];
function upper(array, target, start, end) {
  let ans = -1;
  while (start <= end) {
    let mid = Math.floor((start + end) / 2);
    if (array[mid] === target) {
      ans = mid;
      start = mid + 1;
    } else if (array[mid] > target) {
      end = mid - 1;
    } else {
      start = mid + 1;
    }
  }
  return ans;
}
function lower(array, target, start, end) {
  let ans = -1;
  while (start <= end) {
    let mid = Math.floor((start + end) / 2);
    if (array[mid] === target) {
      ans = mid;
      end = mid - 1;
    } else if (array[mid] > target) {
      end = mid - 1;
    } else {
      start = mid + 1;
    }
  }
  return ans;
}

second.forEach((el) => {
  const lowerIdx = lower(first, el, 0, N - 1);
  const upperIdx = upper(first, el, 0, N - 1);
  if (lowerIdx !== -1 && upperIdx !== -1) {
    answer.push(upperIdx - lowerIdx + 1);
  } else {
    answer.push(0);
  }
});
console.log(answer.join(' '));