[BEAKJOON / node.js] 1920 수 찾기

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

// test.txt
5
4 1 5 2 3
5
1 3 7 9 5

---

sol1

let [_, N, $, M] = require('fs').readFileSync('test.txt').toString().trim().split('\n');
let set = new Set(N.split(' '));
let answer = M.split(' ').map(v => set.has(v) ? 1 : 0).join('\n');
console.log(answer);
// 1
// 1
// 0
// 0
// 1

Set에 담아서 해당 요소가 있는지 확인하고 출력하면 된다. 처음엔 N 배열을 받아서 바로 includes 메서드를 사용해 일치하는 요소가 있는지 확인했는데 배열을 바로 사용하면 시간 초과가 뜨고 Set은 이진 탐색보다도 빠르게 출력된다.

>> Set과 Array의 속도차이

 

---

sol2

let input = require('fs').readFileSync('test.txt').toString().trim().split('\n');
let numN = +input[0];
let N = input[1].split(' ').map(Number).sort((a,b) => a-b);
let M = input[3].split(' ').map(Number);

function binarySearch(arr,target,start,end) {
  let mid = 0;
  while(start<=end) {
    mid = Math.floor((start+end)/2);
    if(arr[mid] === target) return mid;
    else if(arr[mid] < target) start = mid +1;
    else end = mid-1;
  };
  return -1;
};

let answer = '';
M.forEach(el => {
  binarySearch(N,el,0,numN-1) !== -1 ? answer +=`1\n`: answer += `0\n`
});
console.log(answer);
// 1
// 1
// 0
// 0
// 1

최근에 이진탐색에 대해 배우기도 했고 마침 이진 탐색으로 풀 수 있는 문제여서 적용해 봤다. 이진 탐색의 경우 Set으로 제출했을 때 보다 출력 시간이 살짝 더 늦게 나오는 것 같다.