https://www.acmicpc.net/submit/1920/84633322
const fs = require('fs');
const inputs = fs.readFileSync('/dev/stdin').toString().trim().split('\\n');
function run(inputs) {
const arr1 = inputs[1].split(' ').map(Number);
const arr2 = inputs[3].split(' ').map(Number);
const result = [];
for (const number of arr2) {
if (arr1.includes(number)) result.push(1);
else result.push(0);
}
return result.join('\\n');
}
console.log(run(inputs))
arr2
를 순회(O(n))하면서 각 요소에 대해 includes
를 실행(O(m)) 하기 때문에 시간복잡도는 O(n*m)이다.function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) return true;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return false;
}
function run(inputs) {
const arr1 = inputs[1]
.split(' ')
.map(Number)
.sort((a, b) => a - b);
const arr2 = inputs[3].split(' ').map(Number);
const result = [];
for (const number of arr2) {
if (binarySearch(arr1, number)) result.push(1);
else result.push(0);
}
return result.join('\\n');
}
arr1
을 정렬하여 이분 탐색한다.