[백준 / 1920/ nodejs] 수찾기 javascript

nodejs로 풀었다.

처음시도했던 방식은 includes를 사용했다.

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

const N = parseInt(input.shift())
const arr = input.shift().split(' ');
const M = parseInt(input.shift())
const arrM = input.shift().split(' ');
arrM.map( e => {arr.includes(e) ? console.log(1) : console.log(0)})

결과는 시간초과

 

1. 이진탐색

그래서 이진탐색으로 시도해봤다.

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

const N = parseInt(input.shift())
const arr = input.shift().split(' ');
const M = parseInt(input.shift())
const arrM = input.shift().split(' ');

arr.sort();

arrM.forEach(e => {
    let l = 0;
    let r = arr.length;
    let res=0; 
    while(l<=r){
        let mid = parseInt((l+r)/ 2);     

        if(e === arr[mid]){
            res=1;
            break;
        }else if(e<arr[mid]){
            r=mid-1;
            
        }else{
            l=mid+1;
        }
        
    }
    console.log(res);
})

이진 탐색을 위해서는

탐색대상이 정렬되어있는 상태여야한다. sort로 정렬해주고. 결과는 0,1로만 표시되기때문에 res를 0으로 초기화하고

찾을때 res를 1로 바꿔주는 식으로 했다. 

탐색 대상의 중간값과 찾을 값을 비교해서 같으면 res를 1로 세팅

값이 mid값보다 작으면 r을 mid-1로 바꿔줘서 탐색 범위를 반으로 줄인다.

크다면 반대로 l을 mid+1로 올려서 탐색 범위를 줄여주는 식으로 진행.

 

2. Set , has 사용

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const N = parseInt(input.shift())
const arr = new Set(input.shift().split(' '));
const M = parseInt(input.shift())
const arrM = input.shift().split(' ');
arrM.forEach( e => {arr.has(e) ? console.log(1) : console.log(0)})

Set으로 중복을 제거하고 has로 내부에 값이 있는지 조회한다. has 메서드는 결과를 boolean으로 뱉어내기 때문에 삼항연산자로 바로 결과를 표시해줬다.

 

 

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

1920번: 수 찾기