숫자 카드

숫자 카드

문제 설명

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.

예제 입력

5
6 3 2 10 -10
8
10 9 -5 2 3 4 5 -10

예제 출력

1 0 0 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) => {
  const N = Number(input[0]);
  const arr1 = input[1].split(" ").map(Number);
  arr1.sort((a, b) => a - b);
  const M = Number(input[2]);
  const arr2 = input[3].split(" ").map(Number);
  const result = Array(arr2.length).fill(0);

  const bis = () => {
    // 가지고 있지 않은 숫자 카드의 원소 만큼 이분탐색 수행
    for (let i = 0; i < M; i++) {
      // left 값 설정
      let left = 0;
      // right 값 설정
      let right = N - 1;
      if (arr2[i] < arr1[left] || arr2[i] > arr1[right]) continue;
      while (left <= right) {
        // 현재 값
        let mid = Math.floor((left + right) / 2);

        // 만약 arr2[i]의 원소가 arr1[mid] 즉 해당 카드가 상근이가 가지고 있는 카드 중 하나라면
        if (arr2[i] === arr1[mid]) {
          // 값 갱신 후 while 문 탈출 후 다음 원소 보러가기
          result[i] = 1;
          break;
        } else if (arr2[i] > arr1[mid]) left = mid + 1;
        else right = mid - 1;
      }
    }
  };
  bis();
  console.log(result.join(" "));
};

solution(input);

아이디어 / 접근법

1. 이진 탐색으로 전체 카드중 상근이가 가지고 있는 카드의 경우 보기
2. 존재하면 result[i] 번째를 1로 바꿔주기
3. 더 큰경우에는 left 값 늘려주고 아니라면 right 값 줄여주기

후기

이분탐색 대표적인 문제 중 하나라고 생각하는데, 아직 이분탐색에서 어떤 값을 기준점으로 두고 문제를 풀어야 할 지 감이 잘 오지 않아서 해맸음 어렵다..