[Leetcode] First Bad Version

Binary Search
- 문제
- 풀이
마무리

이번 글에서 소개해드릴 문제는 leetcode에 있는 알고리즘 프로그램의 또 다른 이진 검색에 대한 문제를 소개해드리도록 하겠습니다.

Binary Search

바이너리 서치에 대한 기본적인 내용은 저번 포스팅에서 소개해드렸기 때문에 바로 문제풀이로 들어가 겠습니다.

문제

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 returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

풀이

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int start = 1;
        int end = n;
        int mid = 0;
        int min = n;
        
        while(start <= end) {
            // 중간값 구하기
            mid = start + (end - start) / 2;
            if (isBadVersion(mid)) {
                min = Math.min(min, mid);
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        
        return min;
    }
}

이 문제의 신기한 점은 이미 구현이 있는 API를 제공한다는 점입니다. 제가 한창 알고리즘 문제를 풀때는 이런 형태의 문제는 없었는데 신선한 느낌을 받았습니다.

이 문제도 동일한 이진 검색 문제입니다. 하지만 저번과 로직이 동일한 코드로 제출하니, TLE가 발생했습니다. 중간 값을 구하는 과정에서 start와 end의 값이 모두 큰 경우, 정수 값에 overflow가 발생해서 mid 값이 음수가 되는 경우가 생겨 TLE가 발생하는 것으로 추측하고 있습니다.

마무리

알고리즘 풀이 능력에 대한 감이 많이 죽어 leetcode를 통해서 다시 한번 감을 살리려고 노력하고 있습니다. 뭐든지 기본이 중요한 법인데 기본기를 잊어간다는 느낌이 들어 다시 알고리즘 풀이 능력 향상에 힘을 쏟으려고 합니다.

읽어주셔서 감사합니다.

#binary search,
#leet code,
#능력 회복하기,
#알고리즘,
#이진 검색

글이 도움이 되셨다면, 커피 한 잔만 사주세요!

Comments

Copied to clipboard

[Leetcode] First Bad Version

Table of Contents

Binary Search

문제

풀이

마무리