First bad version

알고리즘 테스트 공부를 위해 LeetCode에서 난이도 Easy인 문제들부터 풀어보려고 한다.

분명 Easy라고 적혀있는데, 전혀 Easy하지가 않다..

Leetcode - first bad version

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

문제는 아래와 같다.

📌 isBadVersion이라는 API 호출을 최소화해서 bad version을 찾아내는 것이 핵심이다.

const solution = (isBadVersion: (number) => boolean) => {
  return (n: number): number => {
    let left = 1;
    let right = n;

    while (left < right) {
      const mid = Math.floor(left + (right - left) / 2);
	  isBadVersion(mid) ? right = mid : left = mid + 1;
    }

    return left;
  };
};

1. 처음에 'left'와 'right'에 각각 1과 n을 할당하여 찾을 버전의 범위를 정해주었다.

2. while loop을 이용해 left가 right보다 작다면 Binary search를 반복 수행.

   📌 Binary Search는 배열에서 원하는 항목을 효율적으로 찾는 알고리즘이다. 배열 내에서 중간 항목을 선택 후, 원하는 항목과 비교해 해당항목이 중간 항목의 왼쪽에 있는지 오른쪽에 있는지를 결정한다.
   원하는 항목이 중간 항목의 왼쪽 또는 오른쪽 부분에 있다면, 검색 범위를 반으로 줄여서 검색을 반복한다. 이렇게 검색 범위가 줄어들면서 원하는 항목을 최대한 빠르게 찾을 수 있고, isBadVersion API Call도 최소화할 수 있다!
   

3. 중간 항목인 'mid'를 Math.floor()를 이용해 중간 값을 계산한다.

4. 중간 항목인 mid를 isBadVersion 함수를 이용하여 bad version인지를 확인하고, 맞다면 right 변수에 mid를 할당하고 아니라면 left 변수에 mid에 1을 더한 값을 할당한다. 이렇게 하면 검색 범위가 반으로 줄어든다.

5. left가 right와 같아질 때까지 반복해서 같아졌다는 것은 first bad version을 찾았다는 것이고 left를 그대로 return시킨다.

검색 범위를 각 단계마다 반으로 줄여 API Call를 최소화한다. 버전 수가 많아서 n 값이 크다고 해도 최대한 효율적으로 bad version을 찾아낼 수 있다..!

난이도가 Easy인 문제임에도 불구하고, 시간이 꽤나 걸렸다. 알고리즘 공부를 따로 하며 계속 풀다 보면 검색 시간도 줄고 훨씬 나아질 것이라고 믿는다!