수 찾기

문제

언어

  • JavaScript

문제 풀이 step 1

  • 오름차순으로 정렬합니다.
  • 이진 탐색을 이용해서 수의 존재 여부를 파악합니다.

소스 코드

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

const binarySearch = (arr, key, low, high) => {
	while (low <= high) {
		const mid = parseInt((low + high) / 2);

		if (key === arr[mid]) return mid;
		else if (key < arr[mid]) high = mid - 1;
		else low = mid + 1;
	}

	return -1;
};

const solution = (input) => {
	const N = parseInt(input[0]);
	const nArr = input[1]
		.split(" ")
		.map(Number)
		.sort((a, b) => a - b);
	const M = parseInt(input[2]);
	const mArr = input[3].split(" ").map(Number);

	let res = "";
	for (let i = 0; i < M; i++) {
		if (binarySearch(nArr, mArr[i], 0, N - 1) === -1) res += "0\n";
		else res += "1\n";
	}

	console.log(res);
};

solution(input);

후기

  • 이진 탐색은 정렬된 배열을 가지고 한다는 사실을 명심!!
  • sort 함수에 적절한 콜백 함수를 넣어주지 않으면 정렬이 안된다는 것을 깨달았습니다. 수로 이루어진 배열의 경우에는 콜백 함수 없이 sort를 수행하면 정렬될 줄 알았는데 안된다는 것을 확인할 수 있었습니다.