[JAVA] LeetCode Explore - May Week 1 : First Bad Version

Week 1 : First Bad Version

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

 

Example:
Given n = 5, and version = 4 is the first bad version. call isBadVersion(3) -> false call isBadVersion(5) -> true call isBadVersion(4) -> true Then 4 is the first bad version. 

 

 

새우버거의 첫번째 시도

쉽게 가자 히히^ㅡ^  for 문 썼다.

 public class Solution extends VersionControl {
   public int firstBadVersion(int n) {
     for(int i = 1; i <= n; i++){
       if(isBadVersion(i)){
         return i;
       }
     }
     
     return 0;
   }
}

 

결과는 처참

큰 값일 경우 for문을 사용하면 1부터 n까지 검사하는 것이므로 당연하게 Time Limit Exceeded가 나올 수 밖에..

 

재귀함수 이용

중간 숫자부터 검사를 시작하여 중간을 좁혀나가는 방식으로 재귀함수를 이용하였다.

middle 값을 구하는 것은 (startNum+endNum-1)/2 를 통해 구했더니 int 범위를 벗어나서 아래와 같이 할 수 밖에 없었다. (아니면 형변환..) 

public class Solution extends VersionControl {

  public int firstBadVersion(int n) {
    return check(1, n);
  }
  
  private int check(int startNum, int endNum){
    int middleNum = startNum + (endNum-startNum)/2;
    
    boolean middleBool = isBadVersion(middleNum);
      
    if(startNum>=endNum){
      return endNum;
    }
      
    if(middleBool){
      return check(startNum, middleNum);
    }
    else{
      return check(middleNum+1, endNum);
    }
  }
}

 

결과

때에 따라서 25ms까지도 나왔지만 런타임이 제일 적게 나온 것으로 스크린샷 ㅎㅎ

저 천상계에 있는 사람은 대체 뭐하는 사람일까..

재귀함수로 해결한 사람도 있고, 정석으로 이진 탐색 알고리즘을 사용한 사람도 있었다.