[JS] 백준 수 찾기 -시간 초과, 이진 탐색

문제

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보다 작다.

 

 

시도 1. 이중 포문 안되겠지만 해봄

-> 안됨

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

const N = Number(input[0])
const targetNum = input[1].split(" ").map(Number);
const M = Number(input[2])
const numLst = input[3].split(" ").map(Number);



for (let num of numLst){
    let flag = 0
    for (let target of targetNum){
        if (num === target){
            flag = 1;
            break
        }
    }
    console.log(flag)
}

 

안될 것 같았다! 그럼 이진 탐색으로 해야지

쉬운 문제라고 해서 집중 안하고 풀었다가 

1. start, end, mid 초기화 이상한 곳에 해줘서 

2. 타겟 리스트 반대로 적용해서 틀리고 난리남.

 

하여튼 제정신 차리고 이진탐색으로 풀었는데 시간 초과

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

const N = Number(input[0])
const targetNum = input[1].split(" ").map(Number);
const M = Number(input[2])
const numLst = input[3].split(" ").map(Number);

targetNum.sort((a,b)=> a- b)

for (let num of numLst){
    let anwser = 0;
    let start = 0;
    let end = N-1;
    while (start <= end){
        let mid = Math.floor((start + end)/2)
        if(targetNum[mid] > num){
            end = mid-1;
        }else if (targetNum[mid] < num){
            start = mid+1;
        }else{
            anwser = 1;
            break;
        }
    }
    console.log(anwser);
}

왜 이진탐색도 안되지?

->

node.js에서 console.log() 함수가 생각보다 시간을 많이 잡아먹는다고 한다!

 

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

const N = Number(input[0])
const targetNum = input[1].split(" ").map(Number);
const M = Number(input[2])
const numLst = input[3].split(" ").map(Number);

targetNum.sort((a,b)=> a- b)

let answer = '';

for (let num of numLst){
    flag = false;
    let start = 0;
    let end = N-1;
    while (start <= end){
        let mid = Math.floor((start + end)/2)
        if(targetNum[mid] > num){
            end = mid-1;
        }else if (targetNum[mid] < num){
            start = mid+1;
        }else{
            answer += '1\n';
            flag = true;
            break;
        }

    }
    if(!flag){
        answer += '0\n'
    }
}

console.log(answer)

그냥 한번만 로그 찍도록 변경