LeetCode 278(First Bad Version, java)

0. 문제

https://leetcode.com/problems/first-bad-version/

First Bad Version - LeetCode

 

1. 문제 설명

- 문제에서 제품의 개수(= n)가 주어진다.

- 모든 제품은 이전 버전의 제품을 기반으로 생성된다. 

- 그러므로 이전 버전이 잘못된 경우, 이를 기반으로 만들어진 다음 버전 또한 잘못된 제품이 된다.

 

- 문제에서 isBadVersion(int version) 이라는 메서드를 제공한다.

- 버전 정보를 입력하면 해당 버전이 잘못된 제품인지 아닌지를 boolean 자료형으로 결과를 반환한다.

- 해당 제품이 잘못된 제품이라면 true를 반환하고, 올바른 제품이라면 false를 반환한다.

- isBadVersion() 메서드를 최소한으로 호출하여 n개의 제품 중 첫번째로 생성된 잘못된 버전을 찾는 것이 핵심이다.

  

2. 문제 해설

a) 첫 번째 접근

- 우선 n개의 제품을 탐색하면서 메서드 호출 횟수를 최소화 하기 위해서 O(log n)의 시간복잡도를 사용한다.

- 그 이유는 O(log n)이 탐색 시간 복잡도 중 최소 값이기 때문이다.

- 그러므로 이진 탐색을 사용하면서 동시에 two pointers 방법을 사용하여 탐색 효율을 최대화 한다.

 

b) 두 번째 접근

- 문제의 제약에 따르면 제품은 1번부터 시작이다.

- 그러므로 two pointers를 설정할 때, 시작(= start) index는 1번이 된다.

- 마지막(= end) index는 제품의 개수(= n)와 동일하다. 

 

- 여기서 start는 가장 이전 버전의 제품을 가리킨다.

- 그리고 end는 가장 최신 버전의 제품을 가리킨다. 

 

c) 세 번째 접근

- 중간(= mid) index를 계산한다.

- 중간 index를 계산하는 공식은 다음과 같다.

    → start + (end - start) / 2

 

- mid를 계산하는 과정에서 (end - start) / 2는 알아두면 좋은 트릭이자 노하우다. 

- (end - start)를 수행하는 이유는 mid를 계산할 때 n의 표현 범위를 초과하지 않기 위해서다.

- 다음 문제의 제약 조건을 보자.

 

- 문제의 제약을 보면 n(= 제품의 수)의 최대 표현값이 int 자료형의 최대 표현값과 동일하다.

- 만약 end의 값이 최대 값이고 mid를 (start + end) / 2로 계산하는 경우, 오버플로우가 발생한다. 

- 그러므로 이처럼 제약조건에 따른 자료형의 오버플로우를 방지하기 위한 트릭으로 (end - start)를 사용한다.

- 제약조건이 있든 없든, mid를 계산할 때 "start + (end - start) / 2"라는 공식을 사용하기를 권장한다. 

 

d) 네 번째 접근

- isBadVersion(mid)의 반환 값이 true인 경우, 해당 버전 이전의 제품 중 최초의 잘못된 제품이 존재한다는 의미다.

- 그러므로 end는 mid가 되고, 다시 탐색을 시작한다. 

- 탐색을 계속하는 조건은 start가 end보다 작은 경우일 때까지다. 

- 즉, start == end가 되는 경우가 최초의 잘못된 제품을 가리키는 것이다.

 

- 아래의 코드를 보면서 이해해보자.  

3. 정답 코드

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        
        int start = 1;
        int end = n;
        int mid = 0;
        
        while(start < end) {
            mid = start + (end - start) / 2;
            if(isBadVersion(mid)) { // 현재 버전(mid)이 잘못된 제품인 경우
                end = mid; // mid가 최초의 잘못된 제품이거나, mid 이전에 잘못된 제품이 있을수도 있음
            }
            else { // 현재 버전(mid)이 올바른 제품인 경우 
                start = mid + 1; // mid 이후에 잘못된 버전이 있음
            }
        }
        return start; // start == mid 일때 반복문을 탈출한다. 
    }
}