[JS로 푸는 백준] 1920. 수 찾기

접근법

문제를 읽고서 이중 for문을 통해서 구하면 되겠다 생각하고 구현했는데,

문제를 다시 꼼꼼히 읽었봤더니 주어진 N,M에 범위가 존재했다.

결국 알고리즘 분류를 보고 '이분 탐색' 알고리즘을 이용해야한다는 것을 알게되고

이분탐색에 대해 공부하기 시작했다.

이분탐색 (Binary Search)

정렬되어 있는 배열에서 데이터를 찾으려 시도할 때,

순차탐색처럼 처음부터 끝까지 하나씩 모든 데이터를 체크하여 값을 찾는 것이 아니라

탐색 범위를 절반씩 줄여가며 찾아가는 Search 방법이다.

예시를 들어보자,

1 2 3 4 5 6라는 값에서 6을 찾고자 한다면

배열의 중간에 위치한 3이라는 값과 6을 비교한다.

6은 3보다 크므로, 이제 3의 왼쪽에 위치하는 값들은 탐색할 필요가 없으므로

(어차피 3 왼쪽에 있는 수들은 3보다 작기 때문이다)

3의 오른쪽에 있는 값들을 대상으로 탐색을 다시 시도한다.

이제 4 5 6이 남았으므로, 다시 중간값인 5와 찾고자 하는 대상인 6를 비교한다.

6은 5보다 크므로, 5의 오른쪽에 있는 값들을 대상으로만 탐색을 다시 시도한다.

이제 6만이 남았는데 6과 6을 비교하면, 값이 일치하므로 탐색을 종료한다.

풀이과정

이분탐색 알고리즘을 이용해 다시 문제풀이를 해보면

1. 탐색 대상을 정렬해야함 => sort 사용
2. while문을 이분탐색 알고리즘으로 만듬
3. answer출력

const filePath = process.platform === 'linux' ? 'dev/stdin' : './input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const A = input[1].split(' ').map(v=>+v); // 탐색 대상
const B = input[3].split(' ').map(v=>+v);
let answer = [];
A.sort((a,b) => a - b); // 탐색대상을 정렬
B.forEach(v => {
    let start = 0; // 탐색대상의 처음
    let end = A.length - 1;  // 탐색대상의 끝
    let res = false;
    while (start <= end) {
        let mid = parseInt((start + end) / 2); // 탐색대상의 시작과 끝의 중간값
        if (v < A[mid]) { // B배열의 요소가 탐색 대상의 중간값보다 작으면 중간값에 -1을 해서 탐색범위를 반으로 줄임
            end = mid - 1; // 
        } else if (v > A[mid]) { // 반대로 크면, 중간값 + 1해서 탐색 범위를 줄여줌
            start = mid + 1;
        } else {
            res = true;
            break;
        }
    }
    if (res === true) {
        answer.push(1);
    } else {
        answer.push(0);
    }
})
console.log(answer.join('\n'));