https://www.acmicpc.net/problem/1920

처음 제출

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

let nArray = input[1].split(" ").map(Number);
let mArray = input[3].split(" ").map(Number);
nArray.sort();

let answerArray = [];

const middleIndex = nArray.length / 2;
const middleNumber = nArray[Math.floor(middleIndex)];

mArray.forEach((m, idx) => {
  let find = false;
  if (middleNumber > 0 && m <= middleNumber) {
    for (let i = 0; i < nArray.length; i++) {
      if (nArray[i] === m) {
        answerArray.push(1);
        find = true;
        break;
      }
    }
  } else {
    for (let i = nArray.length - 1; i >= 0; i--) {
      if (nArray[i] === m) {
        answerArray.push(1);
        find = true;
        break;
      }
    }
  }
  if (!find) answerArray.push(0);
})

console.log(answerArray.join("\n"));

문제를 보고 이진 탐색을 써야하는 것은 알아챘다. 처음 풀이는 먼저 배열을 정렬 시킨 뒤, 단순히 처음에만 배열을 반으로 쪼개고 중간값보다 크면 왼쪽 부터, 아니면 오른쪽 부터 도는 로직으로 구현했다. 정답은 맞았지만 이진 탐색을 제대로 사용한 것 같지 않아서 다시 풀었다.

최종 제출

let nArray = input[1].split(" ").map(Number);
let mArray = input[3].split(" ").map(Number);
nArray.sort((a, b) => (a - b));
let answerArray = [];

mArray.forEach((m, idx) => {
  let find = false;
  let start = 0;
  let end = nArray.length - 1;
  while (start <= end) {
    let middleIndex = Math.round((start + end) / 2);
    let middleValue = nArray[middleIndex];

    if (middleValue > m) {
      end = middleIndex - 1;
    } else if (middleValue < m) {
      start = middleIndex + 1;
    } else {
      find = true;
      break;
    }
  }
  if (!find) answerArray.push(0)
  else answerArray.push(1);
})

console.log(answerArray.join("\n"))

새로 고친 풀이는 계속 해서 중간 값을 검사하고, 끝 포인터를 줄이거나, 시작 포인터를 늘려 중간 값을 계속 고쳐가며 검사했다.

헤맸던 점..

분명 알고리즘은 맞는 것 같은데 자꾸 정답이 틀렸다고 나왔다. 반례를 찾아보니 주어진 배열이 전부 음수일 경우가 문제 였다. 예를 들어, [2 -5 -6 -1]이 들어 왔을 때 자바스크립트가 지원하는 메서드인 sort()를 쓰면 당연히 작은 순으로 [-6 -5 -2 -1] 을 뱉을 줄 알았다. 하지만 결과는 [-1 -2 -5 -6]이 었다...

이진 탐색을 쓰기 위해서는 배열을 크기 순으로 정렬을 잘 해놓고 시작해야 하는데 이 부분이 문제 였다. 그래서 sort 메서드를 자세하게 더 작성해주었다.. (어쩐지 IDE에서 경고를 뿜더라)