블로그를 이전 중이라 완료되기 전까지는 벨로그에 작성할 계획입니다.
이후 모든 글은 https://weekwith.me 에 작성 예정이니 다른 글이 궁금하시다면 해당 링크를 통해 방문해주세요.본 글은 [ LeetCode ] 278. 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 returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.
제약사항
1 <= bad <= n <= 231 - 1
풀이
접근법
이진 탐색을 통해 문제를 해결할 수 있다.
이때 모든 버전은 이전 버전에 영향을 받기 때문에 가장 작은, 다시 말해 최초로 True 를 반환한 version 값을 찾으면 된다.
따라서 반복문을 돌 때 true 값을 반환할 경우 answer 라는 변수에 값을 계속 재할당하면서 범위를 점차 줄여나가며 최솟값을 계속 찾아나가면 결국 가장 마지막에 할당된 값이 최솟값, 다시 말해 최초로 True 를 반환한 version 값이 된다.
나의 풀이
접근법을 토대로 문제를 해결하면 아래와 같다.
def solution(n: int) -> int:
start, end, answer = 1, n, 0
while start <= end:
middle: int = (start + end) // 2
if isBadVersion(middle):
answer = middle
end = middle - 1
else:
start = middle + 1
return answer시간 복잡도
이와 같이 문제를 풀 경우 시간 복잡도는 O(logN)이다.
