101. 이것이 코딩 테스트다 7장 : 부품 찾기 Javascript

1. 문제에 대한 이해

• 우리가 풀어야 할 문제는 무엇인가?
   - 손님이 요청한 부품 번호의 순서대로 부품을 확인해 부품이 있으면 yes, 없으면 no를 출력하라
• 주어진 자료는 무엇인가?
   - N = 동빈이가 가지고 있는 부품
   - M = 손님이 요청한 부품

2. 계획

• 이 문제를 푸는데 있어서 유용하게 쓸 수 있는 지식은 무엇인가?
   - 이진탐색

1. N을 정렬 시킨다.
2. M의 요소 하나하나를 N에서 이진탐색을 하면서 N의 요소와 일치하는지 확인한다.
3. 부품이 있으면 yes를 리턴하고 없으면 no를 리턴한다.

3. 실행

• 풀이 계획을 실행하고, 각 단계가 올바른지 점검하라.

첫번째 풀이

const solution = (N, M) => {
  let result = [];

  for (i = 0; i < M.length; i++) {
    if (N.includes(M[i])) {
      result.push('yes')
    } else {
      result.push('no')
    }
  }

  return result.join(' ')
}

test('findStuff', () => {
  expect(solution([8, 3, 7, 9, 2], [5, 7, 9])).toEqual('no yes yes')
});

4. 반성

이진탐색으로 풀어보려다가 구현하는게 어려워서 재귀 사용해서 풀어보려고 했는데 이것도 잘 안됐다. 

그래서 for문을 사용해서 풀었다. 

재귀랑 이진탐색을 사용해서 다시 풀어봐야겠다.

 

 

 

 

두번째 풀이는 이진탐색과 재귀를 사용했다.

const binarySearch = (array, target, start = 0, end = array.length - 1) => {
  const mid = Math.floor((start + end) / 2);
  if (target === array[mid]) {
    return true;
  }

  if (start > end) {
    return false;
  }

  if (target > array[mid]) {
    return binarySearch(array, target, mid + 1, end);
  } else {
    return binarySearch(array, target, start, mid - 1);
  }
};

const run = (array, targets, result = []) => {
  if (targets.length === 0) {
    return result;
  }

  const [target] = targets;

  const found = binarySearch(array, target);
  return run(array, targets.slice(1), [...result, found]);
}

const solution = (N, M) => {
  const array = [...N].sort((a, b) => a - b);
 
  return run(array, M).map((it) => it ? "yes" : "no").join(" ");
};

 

 

 

세번째 풀이는 이진탐색과 map을 사용했다.

const binarySearch = (array, target, start = 0, end = array.length - 1) => {
  const mid = Math.floor((start + end) / 2);
  if (target === array[mid]) {
    return true;
  }

  if (start > end) {
    return false;
  }

  if (target > array[mid]) {
    return binarySearch(array, target, mid + 1, end);
  } else {
    return binarySearch(array, target, start, mid - 1);
  }
};

const run = (array, targets, result = []) => {
  if (targets.length === 0) {
    return result;
  }

  const [target] = targets;

  const found = binarySearch(array, target);
  return run(array, targets.slice(1), [...result, found]);
}

const solution = (N, M) => {
  const array = [...N].sort((a, b) => a - b);
  return M.map((it) => binarySearch(array, it))
    .map((it) => it ? "yes" : "no").join(" ")
};