[BaekJoon] 10815 번 숫자 카드 문제 - (nodejs)

문제 번호 :  10815번

문제 바로가기 ☞ https://www.acmicpc.net/problem/10815

---

 

<<< 문제 내용 >>>

---

 

const { reverse } = require('dns');
const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
let input = fs.readFileSync(filePath).toString().trim().split('\n');

let first_card = input[1].split(' ');
let second_card = input[3].split(' ');
let answer = [];

first_card.sort();

for(let i of second_card){
    answer.push(binarysearch(i, first_card));
}

console.log(answer.join(" "));

function binarysearch(target, array){
    let low = 0;
    let high = array.length-1;

    while(low<=high){
        let mid = Math.floor((low+high)/2);
        
        if(array[mid] === target){
            return 1;
        }else if(array[mid] > target){
            high = mid-1;
        }else{
            low = mid+1;
        }
    }

    return 0;
}

* 이진 탐색(binary search)문제이다.

 

* 궁금한 것은 해시 테이블로 4번째 카드를 넣어두고, 2번째로 키 값들이 있으면 +1 없으면 0 으로 한 후

키 값들을 출력시켜주면 왜 시간초과일까? 머릿 속에선 단순히 O(N+M)에 출력문 정도 +@ 라는 생각이 드는데 O(NlogM)보다 느리게 작동하는 듯 했다.. 왜일까?

 

 

 

 

 

도움이 되셨다면 공감 부탁드립니다.