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

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

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 = [];
second.forEach((el) => {
  let start = 0;
  let middle = 0;
  let end = N - 1;
  let found = false;
  while (start <= end) {
    middle = Math.floor((start + end) / 2);

    if (el < first[middle]) {
      end = middle - 1;
    } else if (el > first[middle]) {
      start = middle + 1;
    } else if (el == first[middle]) {
      answer.push(1);
      found = true;
      break;
    }
  }
  if (!found) {
    answer.push(0);
  }
});

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

첫 번째로 푼 방법은 includes를 사용하여 풀었지만 시간초과가 났다. 이유는 includes를 사용하면 최악의 경우의 수가

500,000 * 500,000 이기 때문이다.

 

두 번째 방법은 배열이 아닌 Set형태로 만들어 has를 사용한 방법이다. 이 경우 500,000이 최악의 수라 통과가 된다. 하지만 문제의 의도는 이게 아니기 때문에 이진탐색 방법을 썼다.

 

첫 번째 숫자 카드를 오름차 순으로 정렬한 다음 중간 값을 기준으로 큰지 작은지 비교하여 범위를 좁혀나가는 방법이다.

우리가 학창 시절에 많이 했던 숫자 업다운으로 맞추는 방법과 동일하다.

 

계속 반의 반의 반의 범위로 줄여 숫자가 있으면 push(1), 숫자가 없을 경우 false의 값을 통해 push(0)을 하면 답이다.