[Leetcode] First Bad Version

문제 출처

• https://leetcode.com/problems/first-bad-version/

First Bad Version - LeetCode

 

문제 해설

• 마지막 버전에서 테스트에서 에러가 발생하였고, 현재 버전은 이전 버전을 기반으로 만들었기 대문에 에러가 발생한 버전 이후로부터 모든 버전에서도 마찬가지로 에러가 발생한다.
• 1부터 n 까지 n 개의 버전이 주어지고 처음 에러가 발생한 버전을 찾아내면 된다.
• 해당 버전이 에러인지 아닌지 판별하는 기준은 isBadVersion API 를 사용하고 에러가 나는 버전이라면 True, 아니라면 False를 반환한다.
  • isBadVersion API 사용을 최소로 하는 알고리즘으로 구성

 

문제 해설

# source: https://leetcode.com/problems/first-bad-version/

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

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

        while left < right:
            mid = (right + left) // 2

            if isBadVersion(mid):
                left = mid + 1
            else:
                right = mid

        return left

• 현재 버전이 이전 버전을 영향을 받고 처음 에러가 발생한 버전 이후 모든 버전은 에러이고, API 사용을 최소로 해야 하기 때문에 이진 탐색을 이용해서 문제를 풀었다.
• 일반적으로 이진 탐색 구성을 가져가되 최초의 에러가 발생한 버전을 찾아야 하므로 반복문의 조건을 left < right 로 주었다.
• 반복문 안에서 left, right을 변경하는 조건으로는 API 결과값으로 이용했고, 에러인 버전인 경우에는 left를 mid + 1 값으로 에러가 아닌 버전인 경우에는 right를 mid 값으로 변경하여 범위를 좁혀주는 방식으로 이용하였다.

 

Github

• https://github.com/limseunghyun95/Algorithm_study/blob/master/leetcode/first_bad_version.py