[LeetCode] 278. First Bad Version (Python3)

솔직히 이거 문제 처음에 이해 못했다. 두 번째 입력되는 숫자 그대로 반환하면 값 그대로 나오기 때문이다. 알고보니 주어진 함수 자체에 bad 파라미터 값이 세팅되어 있지 않아 어쩔수 없이 코딩을 복잡하게 해야했다.

Description

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 returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

풀이

문제에서 제공된 isBadVersion API를 사용하여 해결해야 한다. 그리고 가장 빠르게 값을 구하라고 했기 때문에, 리스트가 정렬된 점을 고려해서 binary search를 이용해야 한다.

데이터 자체가 [1, 2, 3, 4, 5, ... , n]으로 되어있었고, 입력값 자체가 int로 된 점을 고려해 left와 right를 1과 n으로 바로 세팅했다.

맨 위에 말했듯이 '두 번째 숫자 그대로 찾으면' 답인데, 이 두 번째 숫자의 특징으로는 다음과 같다: - isBadVersion(pivot) = true - isBadVersion(pivot - 1) = false

이 조건을 이용해서 코딩을 진행하면 쉽게 문제를 해결할 수 있다.

코드

# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) -> bool:

class Solution:
    def firstBadVersion(self, n: int) -> int:
        left, right = 1, n

        while left <= right:
            pivot = (left + right) // 2
            if isBadVersion(pivot) and not isBadVersion(pivot - 1):
                return pivot
            elif isBadVersion(pivot - 1):
                right = pivot - 1
            else:
                left = pivot + 1