[leetcode, JS] 278. First Bad Version

문제

문제 링크 : First Bad Version

풀이

/**
 * 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) {
        for(let i=1; i<n+1; i++) {
            if(isBadVersion(i)) {
                return i === n ? n : i
            }
            
        }
    };
};

1. isBadVersion이 true가 나올때까지 돌리는 for문
2. 너무 오래 걸린다

• Runtime 9514 ms, Memory 41.9 MB

다른 풀이

/**
 * 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) {
        earliestGood = 0

        while(n - earliestGood > 1) {
            check = Math.floor((n - earliestGood) / 2) + earliestGood
            if (isBadVersion(check)) {
                n = check
            } else {
                earliestGood = check
            }
        }
        return n;
    };
};

1. 반씩 쪼개서 확인해가는 방식

• Runtime 41 ms, Memory 41.9 MB