[백준][자바스크립트][Silver4] 1920 수 찾기

Binary Search 풀이

var fs = require('fs'); 
var input = fs.readFileSync('/dev/stdin').toString().trim().split("\n");

const N = parseInt(input[0]), n = input[1].split(" ").map((num) => parseInt(num)).sort((a, b) => a - b);
const M = parseInt(input[2]), m = input[3].split(" ").map((char) => parseInt(char));
let result = [];

const binarySearch = (arr, start, end, val) => {
    if (start > end) return false;

    const mid = Math.ceil((start + end) / 2);
    if (arr[mid] === val) {
        return true;
    } else if (val < arr[mid]) {
        return binarySearch(arr, start, mid - 1, val);
    } else {
        return binarySearch(arr, mid + 1, end, val);
    }
}

m.forEach((num) => binarySearch(n, 0, n.length - 1, num) ? result.push(1) : result.push(0));
console.log(result.join('\n'));

 

n 을 정렬해주고 m 전체를 루프 돌면서 정렬한 n을 바탕으로 이분 탐색을 통해 m에 있는 내용이 n에 존재하는지 확인해서 result를 찍어준다. 

 

 

Hash 풀이

var fs = require('fs'); 
var input = fs.readFileSync('/dev/stdin').toString().trim().split("\n");

const N = parseInt(input[0]), n = input[1].split(" "), M = parseInt(input[2]), m = input[3].split(" ");
const nHash = {};
let result = [];

for (let i = 0; i < N; i++) {
    if (!nHash[n[i]]) nHash[n[i]] = true;
}

for (let j = 0; j < M; j++) {
    nHash[m[j]] === true ? result.push(1) : result.push(0);
}

console.log(result.join('\n'));

n 으로 nHash 해시를 만들고 m 전체를 루프 돌면서 nHash 에 m 값이 존재하는지 확인해서 result를 찍어준다. 

 

Set 풀이

var fs = require('fs'); 
var input = fs.readFileSync('/dev/stdin').toString().trim().split("\n");

const n = new Set(input[1].split(" ")), M = parseInt(input[2]), m = input[3].split(" ");
let result = [];

for (let i = 0; i < M; i++) {
    n.has(m[i]) ? result.push(1) : result.push(0);
}

console.log(result.join('\n'));

n 을 Set 으로 바로 만들어주고 m 전체를 루프 돌면서 set인 n에 m 값이 존재하는지 확인해서 result를 찍어준다. 

 

 

console.log 주의

 

for (let j = 0; j < M; j++) {
    checker === true ? console.log(1) : console.log(0);
}

 

위처럼 확인하는 부분이 맞으면 1을 console.log 로 찍고, 아니면 0을 console.log 로 직접 찍는 방식으로 구현하면 console.log 의 성능 때문에 전부 시간초과 난다. 아래와 같이 result 배열에 해당 되는 1, 0을 모두 모아서 마지막에 한 번에 console.log 를 찍어줘야 성능 문제가 일어나지 않는다.

 

for (let j = 0; j < M; j++) {
    checker === true ? result.push(1) : result.push(0);
}

console.log(result.join('\n'));