[백준] 2776 암기왕

[Silver 4] 2776 암기왕

문제 링크

구분

알고리즘 > 이분탐색

풀이 요약

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

나의 풀이

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\\n");
const T = +input.shift();
let answer = [];

for (let i = 0; i < T; i++) {
  input.shift();
  const Nnum = input
    .shift()
    .split(" ")
    .map(Number)
    .sort((a, b) => a - b);
  input.shift();
  const Mnum = input.shift().split(" ").map(Number);
  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"));

while (start <= end) 문은 정렬된 수의 배열이 점점 좁혀지다가 탐색 범위가 없으면 루프를 빠져나오게 됩니다.

또한 mid는 현재 탐색 범위의 중간 index를 계산하여 정수 값으로 변환된 값입니다.

**if (v < Nnum [mid])**문은 v가 중간 값인 Nnum [mid]보다 작으면 v는 mid의 왼쪽에 있기 때문에 end를 mid-1로 이동시켜 탐색범위를 왼쪽 절반으로 줄이는 역할을 합니다.

else if (v > Nnum[mid])문은 v가 중간 값인 Nnum [mid]보다 크다면, v는 mid의 오른쪽에 있기 때문에 start를 mid+1로 해주어 탐색범위를 오른쪽 절반으로 줄입니다.

만약 v가 Nnum[mid]와 같으면 즉, 배열에서 찾은값이 v와 같다면 while문을 빠져나와 break 합니다.

배운 점

이전에 풀었던 백준 1920 수 찾기 문제와 똑같지만 테스트케이스를 받아오는 점에서 차이가 있는 문제였습니다.

이분탐색은 정렬된 수를 사용한다는 점을 새로 알게 되었습니다.