LeetCode - First Bad Version

First Bad Version

First Bad Version - LeetCode

 

코드

/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        
        int start = 1;
        int end = n;
        int middle = 1;
        while (start < end) {            
            
            // middle = (start + end) / 2; -> overflow?
            middle = start + (end - start) / 2;
            
            if (isBadVersion(middle)) {                
                end = middle;
                
            } else { 
                start = middle + 1;
            }   

        }
        
        return start;
    }
}

 

문제 설명

주어지는 isBadVersion(int n) 메서드를 활용해서 해당 n번째 버전이 성능 체크에 실패한 버전인지 확인 가능하다. 특정 버전에서 오류가 나면, 그 다음 버전은 이전 버전 기반으로 개발되어서 모두 오류가 난다.

 

즉, (n=7)7개의 버전이 있고, 4번째 버전에서 오류가 난다고 했을때, 해당 메서드로 모두 검사한다면  [false, false, false, true true, true, true] 와 같이 결과가 나온다.

풀이

그냥 for문을 돌려서 1~n 까지 검사하면 시간초과가 나온다. 

 

검색의 효율성을 위해 binarySearch를 활용하는 간단한 문제이다. 그럼에도 불구하고 미친듯이 틀렸다. Discuss에 있는 답안을 봐도 큰 차이가 없는데, 계속해서 시간초과가 나왔다.

 

처음에는 if문 부분을 효율적을 바꾸어야하는 까다로운 문제인가 하는 고민에 다른 코드를 보고, 케이스를 직접 써보면서 확인을 해봤다. 하지만 큰 차이가 없어보였고, 복잡한 조건문을 첨가한 코드도 답안으로 올라와있었다.

 

결론은 탐색을 위한 중간값을 구하는 방법이 문제였다. 잘 보면 입력되는 n의 범위가 1 <= n <=  2^31 - 1 이다. 중간값을 구할 때, middle = (start + end) /2 와 같이 먼저 1과 n을 더해버리면, 오버플로우가 발생할 수 있다.

 

 

middle = (start + end) /2 -> middle = start + (end - start) /2 

 

위와 같이 처음과 끝의 차이를 먼저 구하고, 시작점에서 절반만큼 더하는 방식으로 오버플로우를 방지하면 끝인 간단한 문제였다. 범위를 조심하자는 의미에서 괜히 포스팅 해봤다.