[백준 | JavaScript] 수 찾기 (1920)

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

[ 문제 ]

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

[ 입력 ]

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

[ 출력 ]

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

[ 코드1 ]

이렇게 했더니 시간초과 에러가 뜬다 ........includes가 시간을 너무 잡아먹나보다......

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

const n = parseInt(input[0], 10)
const a = input[1].split(' ').map(Number)
const m = parseInt(input[2], 10)
const x = input[3].split(' ').map(Number)
const result = [];

x.forEach((item) => {
    if(a.includes(item)) result.push(1)
    else result.push(0)
})

console.log(result.join('\n'))

[ 코드2 ]

귀찮지만 이진탐색으로 구현해봤다... 그랬더니 해결되었다...

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split('\n');
const n = parseInt(input[0], 10);
const a = input[1].split(' ').map(Number).sort((a, b) => a - b);
const m = parseInt(input[2], 10);
const x = input[3].split(' ').map(Number);
const result = [];

function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;

    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (arr[mid] === target) {
            return true;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return false;
}

x.forEach((item) => {
    if (binarySearch(a, item)) {
        result.push(1);
    } else {
        result.push(0);
    }
});

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

---