[Day7/15] LeetCode 75

Level 1 : day 7

어느덧 LeetCode 75 Level 1 을 시작한지 7일차다! 이제 반 정도 한거다 :)

오늘의 주제는 어제와 마찬가지로 Binary Search 다.
Binary Search 은 보통 문제에서 주어진 값 중 무엇을 찾아야하며 제한사항에 값이 좀 많다 싶을 때 쓴다. ==> $O(log n)$

가장 기억에 남았던 문제는 카카오 코딩 인터뷰에서 쓰였던 binary search 였는데, 개발자 직군 / 좋아하는 음식 / 등등.. 을 저장 후 점수 몇 점 이상을 걸러야할 때 썼었던거로 기억남는다.

이렇듯, 코딩테스트에서 이진 탐색은 굉장히 중요한 컨셉 중 하나인것은 확실하다!

This study plan is for those who want to prepare for technical interviews but are uncertain which problems they should focus on. The problems have been carefully curated so that levels 1 and 2 will guide beginner and intermediate users through problems that cover the data structures and algorithms necessary to succeed in interviews with most mid-tier companies. While level 3 provides material to help users whose targets are top-tier companies.

704. Binary Search (문제링크)

직관 적인 문제, 배열에 target 을 찾으면 해당 index 을 반환하고, 배열에 없으면 -1 을 반환해야한다.

풀이과정

$O(log n)$ 알고리즘을 사용해서 풀어야하니 이진탐색 (binary search) 을 사용한다.

내가 접해본 사람 중 은근히 mid 값을 단순히 $(low + high) / 2$ 로 계산하는 사람이 많았는데,,,

이 문제에서는 배열의 길이가 크지 않기 때문에 문제가 없지만, 간혹 mid 값 연산 중 int 값보다 커질 때가 생긴다..

따라서 나는 $mid = low + (high - low) / 2$ 로 계산을 한다.

$mid = (low + high) / 2 = low + x$
$x = (high - low) / 2$
$=> mid = low + (high - low) / 2$

Java Solution

class Solution {
    public int search(int[] nums, int target) {
        // O(log n) -> binary search
        
        int low = 0, high = nums.length-1;
        
        while (low <= high) {
            // To avoid a big integer
            // mid = (low + high) / 2 = low + x
            // low + x = (low + high) / 2
            // x = (high - low) / 2
            // mid = low + x = low + (high - low) / 2
            int mid = low + (high - low) / 2;
            
            if (target == nums[mid]) return mid;
            else if (target > nums[mid]) low = mid + 1;
            else high = mid - 1;
        }
        
        return -1;
    }
}

278. First Bad Version (문제링크)

한 번의 bad version 이 생기면 그 후부터 다 bad version 이 된다.
따라서 가장 처음 bad version 을 찾아서 반환해야하는 문제이다.

제한 사항
$1$ $<=$ bad $<= n$ $2^{31} - 1$

풀이과정

가장 처음/ 가장 왼쪽의 bad version 을 찾기 위해 binary search 을 이용하여

1. mid 값이 bad version 이라면 mid 기준 왼쪽을 확인
2. mid 값이 bad version 이 아니라면 mid 기준 오른 쪽을 확인

Java Solution

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int low = 0, high = n;
        // Find left most bad version
        while (low <= high) {
            int mid = low + (high - low) / 2;
            
            if (isBadVersion(mid)) high = mid - 1;
            else low = mid + 1;
        }
        
        return low;
    }
}

binary search 은 이렇게 직관적인 문제들같은 경우 굉장히 쉬운데.. 간혹 써야할 곳이 에매한게 문제다.. 더 많은 문제들을 풀어봐야겠다!