[LeetCode/Kotlin]Easy - 278. First Bad Version

Easy - 278. First Bad Version

문제 해석

총 물건의 개수 n을 입력받는다.

그 중 불량품의 첫 시작을 찾아내는 문제이다.

만약 1~7번까지의 상품이 있는데, 3번이 불량인 경우 3번부터는 모두 불량품이 된다.

문제에서는 input이 n과 bad 두가지 값이라고 나오지만 n만 입력받는다 생각하고 풀면 된다.

---

풀이 방법

풀이 접근 과정

그냥 이진탐색으로 풀면 된다고 생각했다.

아예 예시에서 이진탐색으로 풀도록 알려줘서 접근 자체는 쉬웠다.

 

최종 소스코드

/* The isBadVersion API is defined in the parent class VersionControl.
      fun isBadVersion(version: Int) : Boolean {} */

class Solution: VersionControl() {
    override fun firstBadVersion(n: Int) : Int {
        var left = 0
        var right = n

        while (left < right) {
            val mid = left + (right - left) / 2
            if (isBadVersion(mid)) {
                right = mid
            } else {
                left = mid + 1
            }
        }

        return left
	}
}

1. 왼쪽 경계가 오른쪽 경계보다 작을 때까지 반복하여 이진탐색을 수행한다.

2. 중간 버전이 나쁜 버전인지 확인하여 나쁜 버전이면 오른쪽 경계를 현재 중간 값으로 설정한다. (범위를 좁혀감)

3. 중간 버전이 착한 버전이면 왼쪽 경계를 현재 중간 값으로 설정한다. (범위를 좁혀감)

4. 반복문이 종료되면 left에는 첫 번째 나쁜 버전의 인덱스가 포함되어 해당 값을 반환한다.

---

 

Comment

이 문제는 아예 예시에서

입력: n = 5, bad = 4
 출력: 4
 설명: 
call isBadVersion(3) -> false 
call isBadVersion(5) -> true 
call isBadVersion(4) -> true 
그러면 4가 첫 번째 잘못된 버전입니다.

이렇게 알려줘서 이진탐색으로 접근하는 데 쉬웠다.

다만 문제에서 n과 bad 두개의 값을 입력받는다고 나오는데, bad 값은 사용할 필요가 없어 해당 부분을 이해하는 데에 애먹었다.