[리트코드/자바] 278. First Bad Version

문제

공장에서 상품을 생산할때 품질체크에 문제가 발생했다. 모든 상품은 이전의 상품을 기반으로 개발되었는데, 불량이 발생한 버전 이후의 모든 상품은 불량이다. isBadVersion(version)메소드는 해당 버전이 불량인지 여부에 따라 true/false를 반환한다. n개의 버전 [1,2, ... , n]일 때, 어느것이 가장 최초의 불량버전인지 찾아라. API 호출을 최소화하여 최초의 불량 버전을 찾아라.

 

테스트케이스

• n = 5, bad = 4
  output : 4
• n = 1, bad = 1
  output: 4

 

해설

우리가 찾아야하는 답은 최초의 불량이다. 즉, 불량인 제품 중 이전의 제품이 정상인 것을 찾아야한다는 것이다.

이 문제에서 주목해야할 점은 배열이 아니라 특정 api를 통해서 배열 형태의 자료형을 이용해야한다는 점이다.
배열은 0부터 인덱싱을 하지만, 문제에서는 1번부터 인덱싱한다. 따라서 시작(begin)값은 1이다.

 

로직

1. 전체 버전의 갯수(n)를 기반으로, 최초와 마지막 버전을 지정한다.
2. 최초와 마지막 버전의 중앙 버전의 불량여부를 확인한다.
3. 중앙제품이 불량인 경우,
   1. 해당 제품의 이전 제품이 정상인 경우, 중앙값 리턴
   2. 이전 제품도 불량이라면, 중앙제품 이전 제품을 마지막 버전으로 설정한다
4. 중앙제품이 정상이라면, 중앙제품 다음을 최초 제품으로 설정한다..

 

 

자바 구현코드

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

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        if(n==1) return 1;
        
        
        int begin = 1;
        int end = n;
        int mid = (end - begin) / 2 + begin;
        
        while(true){
            if(isBadVersion(mid)){
                
                if(!isBadVersion(mid-1)){
                    return mid;
                } else {
                    end = mid-1;
                    mid = (end-begin) / 2 + begin;
                }
                
            } else {
                
                begin = mid+1;
                mid = (end-begin) / 2 + begin;
                
            }
        }
    }
}

 

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

First Bad Version - LeetCode