[LeetCode/Kotlin] 278. First Bad Version 답과 해설

문제 링크 : https://leetcode.com/problems/first-bad-version/

First Bad Version - LeetCode

 

 

기본적인 바이너리 서치 문제이나

오버플로우를 주의해야한다...

 

기본적으로 풀이는,

1. 검색 범위의 맨 앞(min 또는 left) 맨뒤(max 또는 right) 인덱스를 저장하는 변수를 설정하고

각각 1과 n으로 초기화 한다.

min은 항상 Not bad version,  max 는 항상 bad version 이라고 가정하고 풀었기 때문에

양 끝값 확인하는 절차로 버전1이 배드버전인지 확인하는 코드를 추가로 넣었다.

 

2. 그 가운데인덱스를 API호출로 확인 후

가운데가 Bad version 이면 max 인덱스를 mid로 옮기고, Bad version 이 아닌 경우 min을 mid로 옮긴다.

여기서 중요한것은 중간값을 구할 때

mid = (min + max) / 2 로 구하면 overflow 가 일어날 수 있으므로

mid = min + (max - min)/2 라고 써줘야한다는 것이다.

 

두 수식은 사람눈에는 비슷하지만 컴퓨터가 볼 때는... 두 수의 합이 자료형 사이즈를 넘어버리면 완전히 다른 식이 된다.

 

3. 이렇게 반복하다가 min 과 max 가 만나면

첫번째 Bad version 은 max 이므로 max를 리턴해주면 된다.

 

 

아래는 내 해답

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

class Solution: VersionControl() {
    override fun firstBadVersion(n: Int) : Int {
        var min = 1
        var max = n
        var mid : Int
        if(isBadVersion(min)) return 1
        
        while(min+1 < max) {
            mid = min + (max-min)/ 2
            if(isBadVersion(mid)) 
            {
                max = mid
            } else {
                min = mid
            }
        }
        return max
	}
}

 

 

isBadVersion API 가 구현이 안 된 상태로 코딩을하려니 디버깅이 어려워서 힘들었다....

오래걸릴줄 알았으면 isBadVersion 구현해서 IDE 디버거를 썼을텐데

흠 개쉽군 하고 그냥 릿코드 사이트에서 풀다가 1시간은 족히걸렸다.... 힝힝

 

프로그래밍 첫 강의에서 배운 자료형의 사이즈..... 역시 기본이 중요한 것이다....