백준 1920번 <수 찾기>

백준 1920번 <수 찾기>

실버 4

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

1920번: 수 찾기

let fs = require('fs');
let [N, a, M, b] = fs.readFileSync('/dev/stdin').toString().split('\n');


let A = a.trim().split(" ").sort();
let B = b.trim().split(" ");

const binarySearch = (array, target, start, end) => {
    let mid = 0;
    while (start <= end) {
        mid = Math.floor((start + end) / 2);

        if (array[mid] == target) {
            return 1;
        }
        if (array[mid] > target) {
            end = mid - 1;
        } else if (array[mid] < target) {
            start = mid + 1;
        }
    }
    return 0;
}

for (let item of B) {
    console.log(binarySearch(A, item, 0, A.length - 1));
}

시간 복잡도 최악의 경우가 100,000 * 100,000 이라서 

"아 이건 분명 이분 탐색이다" 라는 생각을 했습니다...!

 

그래서 이분 탐색을 구현해보았는데...

 

자꾸 시간 초과가 뜨더라구요..!

😭😭 왜지..?

 

도무지 모르겠어서 일단 질문방에 올려봤습니다. 답변이 올라오면 수정해볼게요.

 

그리고 또..!

 

set 객체를 활용하여 푸는 방법을 찾았습니다.

 

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

const [N, A, M, B] = input.map(v => v.split(" "));

const array = new Set(A);

const result = B.map(v => array.has(v) ? 1 : 0);

console.log(result.join("\n"));

set 객체의 has() 메서드를 사용하여 풀었는데

 

이 has() 를 사용하게 되면 시간복잡도가 현저히 줄어들게 되네요...

 

이 has() 가 시간복잡도가 낮은 이유는 좀 더 자료구조, 알고리즘을 공부하고 알려드릴게요...!ㅠㅠㅠ

 

아무튼 map함수를 통해 객체 안에 찾는 요소가 있으면 true 값을, 없으면 false값을 반환하는 has()를 통해 구현하셨네요

 

스트레스 받았습니다. 이 시간 초과를 해결하려다ㅎㅎ

 

 

공부를 더 하고 제대로 올려드릴게요!