[백준 node.js] 1920번 수 찾기 (이진탐색) feat - 시간 초과, 메모리 초과

1920번 수 찾기

레벨: 실버 4

언어: JavaScript

---

문제풀러가기

문제설명

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을 출력한다.

📑풀이 과정

이 문제는 이진탐색으로 문제를 풀 수 있다.

처음에는 includes() 함수로 포함되어 있는지 탐색했고 당연하게도 시간 초과가 나왔다.
includes() 함수의 시간복잡도는 O(n)이다. 선형으로 탐색한다는 말인데
N 과 M이 최대값으로 들어오게 된다면 모든 탐색하는데 10,000,000,000번이 걸릴 것이다.

그래서 이진탐색으로 문제를 풀었다.
이진탐색을 하기 위해서 처음 들어오는 N의 정수들을 정렬한다. 그리고 이진탐색을 구현하면된다.

📋풀이 코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");
const A = input[1].split(" ").map((el) => +el);
const B = input[3].split(" ").map((el) => +el);

solution(A, B);
function solution(N, M) {
  N = N.sort((a, b) => a - b);
  let answer = [];
  M.forEach((el) => {
    let high = N.length - 1;
    let low = 0;
    let find = false; 
    while (low <= high) {
      let mid = Math.floor((high + low) / 2);

      if (el > N[mid]) {
        low = mid + 1;
      } else if (el < N[mid]) {
        high = mid - 1;
      } else {
        find = true;
        break;
      }
    }
    if(find){
        answer.push(1);
    }else{
        answer.push(0);
      }
  });
  console.log(answer.join('\n'))
}

메모리 초과 문제

이진탐색으로 문제를 풀고 제출 했는데 메모리 초과가 발생했다.

아래 처럼 하나 검사할 때 마다 1과 0을 출력하니 메모리 초과가 발생하였다.
그래서 위 풀이 코드와 같이 answer 배열에 저쟝 후 answer을 join하여 출력하니 해결되었다.
메모리 초과가 발생한 이유를 정확히는 모르겠어서 다 공부하고 내용을 추가하겠다.

 

 

메모리 초과가 발생한 코드
console.log(answer ? "1" : "0");

메모리 초과가 해결된 코드
console.log(answer.join('\n'))

---