Leet Code - 278. First Bad Version(C++)

예제: First Bad Version

문제
You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Example:

Given n = 5, and version = 4 is the first bad version.

call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true

Then 4 is the first bad version. 

풀이

처음으로 isBadVersion(version) == true인 version을 리턴하는 문제이다.

성능을 신경쓰지 않은 반복문으로 푼다면 무척 쉽게 풀 수 있지만, 리트코드가 그정도로 만만하지 않다! 당연히 time limit이다.

필자는 0과 n의 가운데 자리에서 시작하여, 반절식 이동하는 방법을 사용하였다.
가운데 자리를 mid라고 하면, 아래와 같은 세 가지 경우가 있을 수 있겠다.

1. isBadVersion(mid) = false && isBadVersion(mid + 1) = false
   이 경우, 왼쪽은 모두 false 이므로 오른쪽으로 (mid + end) / 2만큼 이동한다.
2. isBadVersion(mid) = true && isBadVersion(mid + 1) = true
   이 경우, 오른쪽은 모두 true 이므로 왼쪽으로 (mid + start) / 2만큼 이동한다.
3. isBadVersion(mid) = false && isBadVersion(mid + 1) = true
   답이다. mid + 1을 return한다.

한가지 필자가 실수한 점은, int + int가 있으므로 long 자료형을 썼어야 하는데 그대로 int를 썼던 것이다. 자료형에 유의하자.

전체적인 소스코드는 아래와 같다.

소스 코드

// Forward declaration of isBadVersion API.
bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        
        long start = 0;
        long end = n;
        
        while(end > 1){
            long mid = (start + end) / 2;
            
            //둘다 false
            if(!isBadVersion(mid) && !isBadVersion(mid + 1)){
                start = mid;
            }
            //둘다 true
            else if(isBadVersion(mid) && isBadVersion(mid + 1)){
                end = mid;
            }
            else{
                return mid + 1;
            }
        }
        
        return end;
    }
};

풀이 후기

자료형. 쉬운듯 중요하고 여럽다. 신경쓰자!