문제

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

처음 시도, 실패(시간 초과)

const fs = require('fs')
const input = fs.readFileSync('/dev/stdin').toString().trim()

const solution = (input) => {
    const [a,b,c,d] = input.split('\n')
    return d.split(' ').map(v => {
        let n = b.split(' ').sort((a,b)=>a-b)
        
        while(true){
            let mid = parseInt(n.length/2)
            if(n.length === 0){
                return 0
            }else if(v === n[mid]){
                return 1
            }else if(+v < +n[mid]){
                n = n.slice(0, mid)
            }else if(+v > +n[mid]){
                n = n.slice(mid+1)
            }
        }
    }).join('\n')
}

console.log(solution(input))

다음과 같은 테스트 케이스에서

const input = `5
4 1 5 2 3 11 10 12 9
5
1 3 7 9 5 2 4`

이분 탐색에 대해 나름 이해한대로 구현해보았다. v와 n[mid]를 비교하는데 7 > 11이라는 오류가 발생해서 뭐지?? 하고 콘솔도 찍어보고 한참 들여다봤다. 알고보니 string타입이라서 유니코드 문자를 기준으로 비교한 결과였다는ㅋㅋ +기호를 덧붙여서 number타입으로 변환하여 이 부분은 해결했지만 시간 초과 이슈가 여전히 있었다.
slice를 썼기 때문일까?
slice는 기존 배열에서 얕은 복사로 새 배열을 반환한다.

solution - 이분탐색

const solution = (input) => {
    const [a,b,c,d] = input.split('\n')
    let n = b.split(' ').map(Number)
    let m = d.split(' ').map(Number)
    n.sort((a,b)=>a-b);
  
    return m.map(v => {
        let [s, e] = [0, n.length-1]
        while (s <= e){
            let mid = parseInt((s + e)/2) 
            if (v < n[mid]) { 
                e = mid - 1; 
            }else if (v > n[mid]){ 
                s = mid + 1;
            }else{
                return 1
            }
        }
        return 0
    }).join('\n')
}

시간초과 부분을 해결하기위해 구글링으로 찾은 참고자료를 조금 어레인지했다.
시작s과 끝e의 index를 정의하여 while문의 조건식에 변화를 주었다.
배열객체의 복사 없이 기존 배열의 index값만 다르게 접근해서 그런지 시간초과 이슈 없이 통과했다.

참고 자료

• https://velog.io/@yoseoplee/JS%EB%A1%9C-%ED%91%B8%EB%8A%94-%EB%B0%B1%EC%A4%80-1920.-%EC%88%98-%EC%B0%BE%EA%B8%B0

solution - set

const fs = require('fs')
const input = fs.readFileSync('/dev/stdin').toString().trim()

const solution = (input) => {
    const [a,b,c,d] = input.split('\n')
    const n = b.split(' ').map(Number)
    const m = d.split(' ').map(Number)
    const arr = new Set(n)
    return m.map(v=>arr.has(v) ? 1 : 0).join('\n')
}

console.log(solution(input))

Set을 사용하면 자동정렬을 해줄뿐 아니라 has()메소드를 이용해 객체에 요소가 존재하는지 여부를 알 수 있었다.

참고 자료

• https://gurtn.tistory.com/93