(간단한 코드)리트코드 278. First Bad Version

 

이 문제는 주어진 숫자 n까지 숫자들이 있고, bad라는 숫자 부터 그 뒤의 모든 숫자가 좋지 않다는 뜻을 담고 있다.

 

우리는 bad의 수치를 모르는 상태로, bad의 숫자를 찾는 것이 목표이다.

 

우선 이것은 리스트가 아니므로, 인덱스를 표현하듯이 0부터 시작을 하지 않아야 한다.

코드는 다음과 같다.

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

class Solution:
    def firstBadVersion(self, n: int) -> int:
        
        l,r=1,n
        while l<r: #l과r이 겹치는 부분이 우리가 원하는 부분이므로 등호는 제외한다
                   #실제로 l<r이 아니라 l != r 이라고 해도 동일하게 된다.
            m = (l+r)//2
            if isBadVersion(m):
                r = m #해당 m이 우리가 원하는 숫자일 수 있으니까, 그냥 등호
            else:
                l = m + 1 #해당 m은 우리가 원하는 숫자가 아니므로, m+!
        return l

 

우선 isBadVersion()을 통해서 해당 숫자가 좋은지 나쁜지를 판별하는 함수가 있다고 하며, 이를 사용해서 찾으라고 했다.

 

그냥 for문으로 돌리면, 제출 할때 n=201937523942, bad=123593457398 과 같은 어처구니 없이 큰 숫자를 주기에, 

 

binary search방법으로 풀어야 한다 (여기서 의미하는 binary search는 너비 우선 탐색을 의미하는게 아니다).