[백준 1764] 듣보잡 with Node.js

문제 링크

www.acmicpc.net/problem/1764

1764번: 듣보잡

풀이

const input = require("fs").readFileSync("/dev/stdin").toString().trim().split(/\s/);
const n = +input[0];
const m = +input[1];
const n_arr = input.slice(2, n+2);
const m_arr = input.slice(n+2);

function binary_search(arr, name) {
    let high = arr.length-1;
    let low = 0;
    let mid;

    while (low <= high) {
        mid = Math.floor((high + low)/2);
        if (arr[mid] > name) high = mid - 1;
        else if (arr[mid] < name) low = mid + 1;
        else return true;
    }
    return false;
}
const [long, short] = n_arr.length > m_arr.length ? [n_arr, m_arr] : [m_arr, n_arr];
long.sort();
const dbj = short.filter(name => binary_search(long, name));

console.log(dbj.length+"\n"+dbj.sort().join("\n"));

불린을 반환하는 이진 탐색 함수를 Array.prototype.filter의 콜백함수로 받아서 두 배열에서 겹치는 이름만을 추출해낸다.

 

long, short를 굳이 나눈 이유는 실행 시간을 줄이기 위해서이다. 나누지 않았을 때보다 약 28ms 정도 더 빨라진다.