[알고리즘] #First Bad Version

문제 출처: https://leetcode.com/problems/first-bad-version/

First Bad Version - LeetCode

문제 해석

당신은 프로젝트 관리자이고, 현재 신제품 개발팀을 이끌고 있습니다. 안타깝게도 최신버전 제품이 품질검사에 실패했습니다. 각 버전은 이전 버전을 기반으로 하고 있으며, bad 버전 이후의 모든 버전들 또한 bad 입니다.

당신이 n개의 버전 [1,2,...n] 갖고 있고, 모든 bad 버전들의 기반이되는 최초 bad 버전을 찾고자 한다고 가정해봅시다. 

어떤 version이 bad 버전인지 리턴하는 bool isBadVersion(version)이라는 API가 주어졌을 때, 최초 bad 버전을 찾는 function을 구현하시오. API를 호출하는 횟수는 최소화해야합니다.

 

 

풀이

이 문제도 다른 비교 문제와 마찬가지로 중간값부터 비교를 해서 비교할 배열의 범위를 좁혀나가야한다.

그런데 여기서 조심해야하는 부분은 isBadVersion(version)가 true를 리턴한다고 해서 무조건 해당 version이 bad version은 아니라는 것이다.

처음 코드를 구현할 때에는 변수를 최대한 많이 쓰지 않으려고 bad, mid만 정의해서 사용했다. 그런데 내가 짠 코드지만 디버깅할 때 조금 헷갈렸다. 런타임 84m/s 와 메모리 42MB로 submit은 성공했지만 좀 찝찝해서 다른 사람들 코드와 비교해보았다. 역시 좀 더 간단한 로직으로 짜여진 코드가 있었다.

 

// 처음 짠 코드
var solution = function(isBadVersion) {
    return function(n) {
        let bad = n;
        let mid = parseInt((1+bad)/2);
        while(1) {
            if (isBadVersion(mid)) {
                if (mid < bad) {
                    bad = mid;
                    mid = parseInt((1+bad)/2);
                } else {
                    return bad;
                }
            } else {
                if (bad - mid === 1) {
                    return bad
                }
                mid = parseInt((mid+bad)/2);
            }
        }
    };
};

// runtime 50ms 코드
var solution = function(isBadVersion) {
    return function(n) {
        let start = 1
        let end = n
        
        while(start < end) {
            const mid = Math.floor((start+end)/2)
            if (isBadVersion(mid)) {
                end = mid
            } else {
                start = mid + 1
            }
        }

        return start
    };
};

 

✅ 가독성 좋은 변수 선언

- 일반적으로 다들 변수를 start, end 또는 left, right로 선언해서 사용했다.

- 중간 값(mid)를 선언하여 사용한건 대부분 동일했다.

 

✅ Math.floor() 사용

- Math.floor()는 parseInt()보다 속도가 더 빠르기 때문에 전자를 더 많이 사용했다.

- 두 함수의 차이점은 처리속도도 있지만, 음수인 경우에 차이가 있다.