[알고리즘] LeetCode First Bad Version JS

개요

이렇게 주어지는 문제는 처음이었는데 함수를 전달받고 함수에 버전을 넣으면 bad version인지 아닌지 알려준다. 이를 통헤서 제일 처음 bad version을 찾는 문제이다

First Bad Version - LeetCode

 

 

풀이

투 포인터로 접근을 했었고 그림으로 그려봤을 때 분기 조건으로는 다음과 같았다.

 

1	2	3	4	5
false	false	false	true	true

첫 번째 true가 나오는 조건을 찾는게 문제이니 true쪽으로 움직여야 한다고 생각했다.

1) true가 리턴되면 rt가 mid 앞으로와서  true가 더 나오는지 확인한다.

2) false가 리턴되면 lt를 mid로 올려서 true를 찾아낸다. 

 

이때 true일때 바로 앞이 false일 경우 해당 version이 첫 번쨰 badVersion이므로 리턴하면 된다.

 

마지막으로 접근을 주의해야한다. 기존 배열에서 투포인터를 사용하던대로 아무 생각없이 left를 0부터 시작하고 right를 n - 1부터 시작하는 바람에 조금 헷갈렸다.

/**
 * Definition for isBadVersion()
 *
 * @param {integer} version number
 * @return {boolean} whether the version is bad
 * isBadVersion = function(version) {
 *     ...
 * };
 */

/**
 * @param {function} isBadVersion()
 * @return {function}
 */
var solution = function (isBadVersion) {
  /**
   * @param {integer} n Total versions
   * @return {integer} The first bad version
   */
  return function (n) {
    let lt = 1;
    let rt = n;

    while (lt <= rt) {
      const mid = Math.round((rt + lt) / 2);

      if (isBadVersion(mid) === false) lt = mid + 1;
      else {
        if (isBadVersion(mid - 1) === false) return mid;
        rt = mid - 1;
      }
    }
  };
};