암기왕

암기왕

문제 설명

연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, 연종이 하루 동안 본 정수들을 모두 ‘수첩1’에 적어 놓았다. 그것을 바탕으로 그가 진짜 암기왕인지 알아보기 위해, 동규는 연종에게 M개의 질문을 던졌다. 질문의 내용은 “X라는 정수를 오늘 본 적이 있는가?” 이다. 연종은 막힘없이 모두 대답을 했고, 동규는 연종이 봤다고 주장하는 수 들을 ‘수첩2’에 적어 두었다. 집에 돌아온 동규는 답이 맞는지 확인하려 하지만, 연종을 따라다니느라 너무 힘들어서 여러분에게 도움을 요청했다. 동규를 도와주기 위해 ‘수첩2’에 적혀있는 순서대로, 각각의 수에 대하여, ‘수첩1’에 있으면 1을, 없으면 0을 출력하는 프로그램을 작성해보자.

예제 입력

1
5
4 1 5 2 3
5
1 3 7 9 5

예제 출력

1
1
0
0
1

---

문제 풀이

const fs = require("fs");
const path = require("path");
const input = fs
  .readFileSync(
    process.platform === "linux"
      ? "/dev/stdin"
      : path.join(__dirname, "input.txt")
  )
  .toString()
  .trim()
  .split("\n");

const solution = (input) => {
  let idx = 0;
  const T = Number(input[idx++]);
  for (let tc = 0; tc < T; tc++) {
    const N = Number(input[idx++]);
    const arr1 = input[idx++].split(" ").map(Number);
    arr1.sort((a, b) => a - b);
    const M = Number(input[idx++]);
    const arr2 = input[idx++].split(" ").map(Number);
    const result = Array(arr2.length).fill(0);

    const bis = () => {
      for (let i = 0; i < M; i++) {
        let left = 0;
        let right = N - 1;

        while (left <= right) {
          let mid = Math.floor((left + right) / 2);
          // arr2 즉 수첩2 수첩1 의 값이 존재하면
          if (arr2[i] === arr1[mid]) {
            // result 배열 재할당 후 종료
            result[i] = 1;
            break;
          }
          // 이분 탐색으로 범위 설정
          else if (arr2[i] > arr1[mid]) left = mid + 1;
          else right = mid - 1;
        }
      }
    };
    bis();
    console.log(result.join("\n"));
  }
};
solution(input);

아이디어 / 접근법

1. 수첩2의 원소만큼 반복문을 돌려서 수첩 1에 존재 하는 지 판별
2. 존재하면 result 배열에 할당 후 종료
3. 더 큰경우에는 left 값 늘려주고 아니라면 right 값 줄여주기

후기

두 가지의 배열이 주어지고 해당 배열을 통해 이분탐색을 진행하는 좋은 예시라고 생각했음