LeetCode 278 (Easy) First Bad Version

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

First Bad Version - LeetCode

문제

한글 번역은 아래 더보기를 클릭해주세요.

당신은 새 서비스를 개발하기 위해 팀을 리딩하고 있는 프로젝트 매니저이다. 안타깝게도, 서비스의 최신 버전이 품질 검사를 통과하지 못했다. 각각의 버전은 이전 버전을 기반으로 개발되기 때문에, 문제가 된 버전 이후의 모든 버전은 품질 검사를 통과하지 못한다. 

n개의 버전 [1, 2, ..., n]이 있다고 할 때, 문제가 된 최초의 버전을 찾아라.

 

API bool isBadVersion(version)은 version의 품질 검사 통과 여부를 리턴한다. API 호출은 최소화하여 문제가 된 최초의 버전을 찾아라.

 

예제 1:

• 입력: n = 5, bad = 4
• 출력: 4 
• 설명:
  isBadVersion(3) 호출 -> false
  isBadVersion(5) 호출 -> true
  isBadVersion(4) 호출 -> true
  버전 4가 최초로 문제가 된 버전이다. 

예제 2:

• 입력: n = 1, bad = 1
• 출력: 1

제약조건:

•  1 <= bad <= n <= 2^31 - 1

풀이

• 정렬된 버전 정보가 있고, 탐색(API 호출)을 최소화하는 것이므로 이진탐색으로 문제를 푼다
• isBadVersion(version) == true 이면 답 후보로 version 저장, 이전 버전들 탐색
• isBadVersion(version) == false 이면 답 후보로 version + 1 저장, 이후 버전들 탐색

python

이진탐색 반복문

# The isBadVersion API is already defined for you.
# @param version, an integer
# @return an integer
# def isBadVersion(version):

class Solution:
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        """
        - 이진탐색
        - isBadVersion(version) == true 이면 답 후보로 version 저장, 이전 버전들 탐색
		- isBadVersion(version) == false 이면 답 후보로 version + 1 저장, 이후 버전들 탐색
        """
        start = 1
        end = n
        result = 0
        
        while start <= end:
            mid = (start + end) // 2
            
            if isBadVersion(mid) == 1:
                end = mid - 1
                result = mid
            else:
                start = mid + 1
                result = mid + 1
        
        return result
        

이진탐색 재귀문

# The isBadVersion API is already defined for you.
# @param version, an integer
# @return an integer
# def isBadVersion(version):

class Solution:
    def findBad(self, start, end, version):
        if start > end:
            return version
        
        mid = (start + end) // 2
        
        if isBadVersion(mid) == 1:
            return self.findBad(start, mid - 1, mid)
        else:
            return self.findBad(mid + 1, end, mid + 1)
        
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        """
        - 이진탐색
        - isBadVersion(version) == true 이면 답 후보로 version 저장, 이전 버전들 탐색
		- isBadVersion(version) == false 이면 답 후보로 version + 1 저장, 이후 버전들 탐색
        """
        return self.findBad(1, n, n)

 

결과