LeetCode/Grind169

278. First Bad Version ★★★

hyunkookim 2025. 4. 22. 07:03

278. First Bad Version

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

class Solution:
    def firstBadVersion(self, n: int) -> int:
        # 가장 빨리 나오는 bad 버전 찾기..
        # 그러니깐. 경계
        # isBadVersion(n) 했는데, bad 이면, n-1로 옮기고.
        l, r = 1, n+1
        fisrtBad = n 

        while l<=r: 
            m = (l+r)//2
            if isBadVersion(m): # true 이면, m 뒤에것이 false
                l = m+1
            else:
                # false 이면, m 앞에것이 true 일 가능성이
                # 근데 첫 false 를 찾아야 함
                fisrtBad = min(fisrtBad, m)
                r = m-1
        return fisrtBad

 

지금 아이디어는 **이진 탐색(Binary Search)**을 이용한 것이고 방향도 거의 맞지만,

조건 해석이 반대로 되어 있어 결과가 잘못될 수 있습니다.

❗ 현재 코드의 문제점 요약

if isBadVersion(m):
    l = m + 1  # ❌ 실제로는 m이 bad이면, 답이 m 또는 그보다 작을 수 있음
else:
    fisrtBad = min(fisrtBad, m)
    r = m - 1

→ isBadVersion(m)이 True면, 그게 답일 수도 있어서 r = m - 1로 줄여야 하고
→ isBadVersion(m)이 False면, 답은 오른쪽에 있으므로 l = m + 1로 가야 합니다.

 

최종 코드

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

class Solution:
    def firstBadVersion(self, n: int) -> int:
        # 가장 빨리 나오는 bad 버전 찾기..
        # 그러니깐. 경계
        # isBadVersion(n) 했는데, bad 이면, n-1로 옮기고.
        l, r = 1, n+1
        fisrtBad = n # 가능한 가장 뒤 bad 버전으로 초기화

        while l<=r: 
            m = (l+r)//2
            if isBadVersion(m): # true 이면, 현재 bad 이니, 앞에 것에 true 일 가능성이
                # 근데 첫 false 를 찾아야 함
                fisrtBad = min(fisrtBad, m)
                r = m-1
            else:
                # false 이면, 현재 good 이니, m 뒤에 것이 true 일 가능성이
                l = m+1
        return fisrtBad

 

left <= right 에서 = 이 꼭 필요한지?
 

ChatGPT의 말:

아주 좋은 질문이에요!
이진 탐색에서 while left <= right: 에서 **= (등호)**가 꼭 필요한지 여부는 탐색 범위가 닫힌 구간인지 열린 구간인지에 따라 달라집니다.

✅ 현재 코드: left, right 모두 포함하는 닫힌 구간 [left, right]

while left <= right:  # ⬅️ 이건 [left, right] 범위를 의미
  • 예를 들어 left == right일 때도 확인해야 하는데, 이때 =가 없으면 마지막 남은 값을 확인하지 못하고 탐색이 끝나버립니다.
  • 그래서 **반드시 등호(=)**가 필요합니다.

❌ 만약 while left < right:를 쓴다면?

이건 [left, right) 반열린 구간입니다.
이 경우엔 right = mid 로 업데이트하고, 종료 조건이 left == right일 때 멈추므로
루프 밖에서 left 또는 right 가 곧 정답이 됩니다.

🔁 두 방식 비교 요약

방식 루프 조건 isBadVersion(mid)일 때 종료 후 리턴
닫힌 구간 while left <= right: right = mid - 1 first_bad
반열린 구간 while left < right: right = mid left 또는 right
(왜냐, 이때는 left == right 시 loof 종료)

✅ 현재 코드 방식에서는 등호 = 꼭 필요합니다

while left <= right:  # 마지막 하나도 확인해야 하므로 '=' 필수

예를 들어:

n = 1, isBadVersion(1) == True

이 상황에서 while left < right:이면 루프 자체가 실행되지 않고 종료됩니다.

 

반열린 구간을 쓸 거면 ??

class Solution:
    def firstBadVersion(self, n: int) -> int:
        l, r = 1, n  # 반열린 구간: [l, r)

        while l < r:
            m = (l + r) // 2
            if isBadVersion(m):
            	"""
                m도 bad일 수 있으므로 포함시킴
                """
                r = m  
            else:
                l = m + 1  # m은 good이므로 버림

		"""
        종료 시점에 l == r == 정답
        return r 해도 됨!!
        """
        return l

 

아래 처럼 m 위치가 Bad 일때, r을 m 을 포함하지 않고, m-1로 줄이면 안됨!!

=> 왜냐? m 위치가 첫 Bad 일수도 있음, 따라서, r = m 으로 하고, m 을 포함하게 해야 함

if isBadVersion(m): 
    r = m - 1

 

  • isBadVersion(m)이 True면 m이 첫 bad version일 수도 있으므로, r = m - 1로 줄여버리면 m 자체를 무시해버립니다.
  • 그래서 마지막에 return l 했을 때 실제로 첫 bad version보다 커져 있을 수 있어요.

👇 왜 l < r인가?

while l < r:
    m = (l + r) // 2
    if isBadVersion(m):
        r = m
    else:
        l = m + 1
return r

이 구조에서는 r = m을 사용하고 있기 때문에,
r을 포함한 왼쪽 범위를 유지하려고 해요.

예시: n = 5, 처음 bad version이 4일 때

  • isBadVersion(3) → False → l = 4
  • isBadVersion(4) → True → r = 4
  • 이제 l == r == 4 → 종료되고 return r

만약 이때 while l <= r을 쓰면?

  • 마지막 반복에서 l == r == 4이고
  • m = 4, r = 4가 그대로 유지되고
  • 다음 루프 진입 → 무한 루프 가능성 or 잘못된 결과

🔑 정리:

  • r = m 같은 왼쪽 포인터 유지형 이분 탐색에서는 → while l < r
  • l = m + 1, r = m - 1로 정확히 줄이는 경우에는 → while l <= r

📌 외우는 팁:

  • r = m 쓸 거면 while l < r
  • r = m - 1 쓸 거면 while l <= r

세번째 시도..또 틀림 !!

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

class Solution:
    def firstBadVersion(self, n: int) -> int:
        # g,g,g,b,b,b, 이렇게 되어있을때 첫번째 bad 의 인덱스 찾기
        l, r =1, n
        first_bad = n # 최소값 찾는 문제
        while l<=r:
            m = (l+r)//2
            # isBadVersion(m)가 True이면 bad, False 이면 good
            if isBadVersion(m):
                 first_bad = min(first_bad, m)
                 # 왼쪽으로 더 갈수있을지도
                 r = m # 근데, 현재가 첫 Bad 일수도있어서, m-1하면 안됨
            else:
                l=m+1

        return first_bad

 

코드 흐름은 거의 맞는데, 핵심 문제는 여기입니다: r = m

이렇게 하면 무한 루프에 빠질 수 있습니다.

왜냐하면 l == r일 때

m = (l + r) // 2 = l = r이 되어서 r을 m으로 바꾸면 r은 그대로고,

l도 그대로라서 l <= r 조건이 계속 유지되며 무한히 반복됩니다.

✅ 올바른 수정:

r = m - 1로 해야 한 칸 왼쪽으로 줄어듭니다.

if isBadVersion(m):
    first_bad = m
    r = m - 1

first_bad = min(first_bad, m)는 어차피 m이 더 작을 때만 덮어씌우기 때문에, 그냥 first_bad = m으로 바꿔도 됩니다.

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

class Solution:
    def firstBadVersion(self, n: int) -> int:
        # g,g,g,b,b,b, 이렇게 되어있을때 첫번째 bad 의 인덱스 찾기
        l, r =1, n
        first_bad = n # 최소값 찾는 문제
        while l<=r:
            m = (l+r)//2
            # isBadVersion(m)가 True이면 bad, False 이면 good
            if isBadVersion(m):
                # first_bad = min(first_bad, m)
                first_bad = m

                # 왼쪽으로 더 갈수있을지도
                r = m-1 
                """
                근데, 현재가 첫 Bad 일수도있어서, m-1하면 안된다고 생각할수도 있지만,

                l == r일 때
                m = (l + r) // 2 = l = r이 되어서 r을 m으로 바꾸면 r은 그대로고,
                l도 그대로라서 l <= r 조건이 계속 유지되며 무한히 반복됩

                그리고, first_bad = min(first_bad, m)는 어차피 m이 더 작을 때만 덮어씌우기 때문에, 
                그냥 first_bad = m으로 바꿔도 됨
                """
            else:
                l=m+1

        return first_bad