[백준 문제풀이] 10815번 숫자 카드

10815 숫자 카드

문제 설명

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

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다

출력

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 가지고 있으면 1을, 아니면 0을 공백으로 구분해 출력한다.

문제 풀이

강의에서 이진 탐색으로 풀어보라고 해서 이진 탐색으로 풀어보았다.

이진 탐색이란?

정렬되어 있는 리스트색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법.
이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정.
매 탐색마다 길이를 2로 나누어 탐색하기 때문에 O(log N)의 시간복잡도를 가진다.

📌 이진 탐색의 구현
1. 배열의 가운데 값 arr\[mid]을 찾는다.
2. arr\[mid]가 찾으려는 값보다 작은지/큰지 비교하여 나머지 탐색을 가운데 기준으로 왼쪽/오른쪽을 탐색한다.
3. 그 과정에서 같은 값을 찾으면 1을 반환한다.

이진 탐색은 정렬된 리스트에서 가능하기 때문에 입력값 배열 numCards는 sort() 함수로 정렬해주었다.

// 백준 10815번 숫자 카드

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

const n = Number(input.shift());
const numCards = input
  .shift()
  .split(" ")
  .map(Number)
  .sort((a, b) => a - b);

const m = Number(input.shift());
const test = input.shift().split(" ").map(Number);

const binarySearch = (arr, target, start, end) => {
  if (start > end) return 0;
  let mid = parseInt((start + end) / 2);
  if (arr[mid] == target) return 1;
  else if (arr[mid] > target) return binarySearch(arr, target, start, mid - 1);
  else return binarySearch(arr, target, mid + 1, end);
};

let result = "";
for (let i = 0; i < m; i++) {
  result += binarySearch(numCards, test[i], 0, n - 1) + " ";
}

console.log(result);