[javaScript] 백준1920번 수찾기

처음 생각한 알고리즘 !

보자마자 너무 간단한 문제라고 생각이 들었다 그냥 배열에 담아주고 정렬해준뒤 includes 써서 true 일때 반환하면 되는거 아닌가?

그렇게 나의 첫번째 코드

const filePath = process.platform === 'linux' ? 
'/dev/stdin' : 'example.txt';

let input = require('fs').readFileSync(filePath).toString().trim();
input = input.split("\n");
L = input.shift().split(' ').map(Number);
input = [...input].map(x => x.replace("\r", ""));
let number;
let check;
for (let i = 0; i < L; i++){
    number = input[0].split(' ');
    
}

for (let i = 0; i < input[1]; i++){
    check = input[2].split(' ');
    if (number.includes(check[i])) {
        console.log(1);
    } else {console.log(0);}
}

그치만 이 코드는 메모리 초과로 인해 실패 하였다. 처음에는 코드가 문제인가 싶었지만 이내 시간복잡도 문제란걸 깨달았다.(어쩐지 문제가 너무 쉽더라) 숫자가 커지면 이중for문을 돌리면서 시간 복잡도가 O=n^2 을 가지게 되며 이를 해결하기위해 for문으로 다 찾는게 아닌 이진 탐색 알고리즘을 떠올리게 되었다.

---

이진탐색 알고리즘이란?

시작인덱스와 끝 인덱스를 초기 값으로 놓고 둘이 더한 뒤 2로 나누어 그 중간값을 기준으로 타겟이 중간값 보다 작은지 큰지를 비교하여 범위를 좁혀가면서 찾는 방식이다. 이를 통하여 연산횟수를 대폭 줄 일수 있으며 코드는 다음과 같다.

const filePath = process.platform === 'linux' ? 
'/dev/stdin' : 'example.txt';

let input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const [L, number, M, checks] = input;

const numbers = number.split(' ').map(v => +v);
const check = checks.split(' ').map(v => +v);

numbers.sort((a, b) => a - b);

check.forEach(v => {
    let low = 0;
    let high = numbers.length - 1;
    let mid;
    while (low <= high) {
        mid = parseInt((low + high) / 2);
        if (numbers[mid] === v) return console.log(1);
        else if (numbers[mid] > v) high = mid - 1;
        else low = mid + 1;
    }
    return console.log(0);
}
)