[백준] 1920 수 찾기

[Silver 4] 1920 수 찾기

문제 링크

구분

알고리즘 > 이분탐색

풀이 요약

이분탐색을 활용하여 주어진 배열에 해당 숫자가 존재하는지 풀어내는 문제

나의 풀이

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

const N = Number(input[0]);
let Nnum = input[1].split(" ").map(Number);
const M = Number(input[2]);
let Mnum = input[3].split(" ").map(Number);
const answer = [];

Nnum.sort((a, b) => a - b);
Mnum.forEach((v) => {
  let start = 0;
  let end = Nnum.length - 1;
  let isNumberInArray = false;

  while (start <= end) {
    let mid = parseInt((start + end) / 2);
    if (v < Nnum[mid]) {
      end = mid - 1;
    } else if (v > Nnum[mid]) {
      start = mid + 1;
    } else {
      isNumberInArray = true;
      break;
    }
  }
  isNumberInArray ? answer.push(1) : answer.push(0);
});

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

배운 점

이분탐색에 대해 실제로 알고리즘을 구현하면서 이분탐색이 어떻게 탐색하는지 그 방법에 대해 알 수 있었습니다.

대게 이분탐색은 결정 문제(Decision Problem)의 답이 이분적일 때 사용할 수 있는 탐색기법이기 때문에 답이 Yes or No인 문제에 사용됨을 알게 되었습니다.

처음 푸는 문제라 이분탐색 수도코드를 참고하여 작성된 코드입니다.