한 회사에서 어떤 제품 관리자가 새로운 제품을 개발하는 팀을 이끌고 있다고 가정해 봅시다. 최신 버전이 품질 검사에서 통과하지 못했고, 각 버전은 이전 버전을 기반으로 개발되기 때문에 한 번 잘못된(bad) 버전이 나오면 그 이후의 모든 버전 역시 잘못된 버전이 됩니다. 따라서 [1, 2, …, n]의 n개 요소로 이루어진 배열 A가 주어졌을 때, 우리는 이 배열에서 첫 번째 잘못된 버전을 찾아야 합니다.
이 문제에서는 특정 버전이 잘못된 버전인지 여부를 알려주는 함수 isBadVersion(version_id)를 사용할 수 있습니다. 예를 들어 n = 5이고 4번 버전이 첫 번째 잘못된 버전이라고 가정해 보겠습니다. 이때 isBadVersion(3)은 False를 반환하고, isBadVersion(4)와 isBadVersion(5)는 True를 반환한다면, 첫 번째 잘못된 버전은 4입니다.
문제 해결 접근 방법
이 문제는 다음 두 가지 단계로 해결할 수 있습니다.
- n이 2 미만이라면 해당 값(n)을 그대로 반환합니다.
- 주어진
isBadVersion함수를 활용하여 이진 탐색(binary search) 방식으로 첫 번째 잘못된 버전을 효율적으로 찾습니다.
예제 코드
다음 파이썬 구현 예제를 통해 더 자세히 이해해 보겠습니다.
first_bad = 0
def isBadVersion(version):
if version >= first_bad:
return True
return False
class Solution:
def firstBadVersion(self, n):
if n < 2:
return n
start = 1
end = n
while start <= end:
mid = (start + end) // 2
if isBadVersion(mid) and not isBadVersion(mid - 1):
return mid
elif isBadVersion(mid - 1):
end = mid - 1
else:
start = mid + 1
ob1 = Solution()
first_bad = 4
op = ob1.firstBadVersion(5)
print(op)
동작 원리
위 코드는 탐색 범위의 시작점(start)과 끝점(end)을 설정한 뒤, 중간 지점(mid)을 반복적으로 확인합니다. 만약 mid 버전이 잘못된 버전이면서 바로 앞 버전(mid - 1)은 정상 버전이라면, mid가 곧 첫 번째 잘못된 버전입니다. 앞 버전도 이미 잘못된 버전이라면 탐색 범위를 왼쪽으로 좁히고, 그렇지 않다면 오른쪽으로 좁혀 나갑니다. 이러한 이진 탐색 덕분에 선형 탐색(O(n)) 대신 O(log n)의 시간 복잡도로 빠르게 답을 구할 수 있습니다.
입력
5
4
출력
4