[LeetCode] 35. Search Insert Position

Search Insert Position - LeetCode

정렬된 int 배열과 target 넘버가 주어지면 배열중에서 target이 들어갈 위치가 어디인지 반환하는 문제입니다.

입출력 예시와 함께보면 쉽게 이해할 수 있습니다.

 

Example 1:

Input: nums = [1,3,5,6], target = 5
Output: 2

Example 2:

Input: nums = [1,3,5,6], target = 2
Output: 1

Example 3:

Input: nums = [1,3,5,6], target = 7
Output: 4

 

문제 접근

단순히 for-loop를 이용해 target이 어디에 들어가는지 분기처리를 하여 찾고 반환하였습니다.

 

    public int searchInsert(int[] nums, int target) {

        for (int i = 0; i < nums.length; i++) {
            if (target > nums[i]) {
                continue;
            }
            if (target <= nums[i]){
                return i;
            }
        }

        return nums.length;
    }

문제는 정답을 받았습니다.

하지만 문제의 요구사항은 O(log n)의 시간복잡도가 필요합니다...

 

O(log n) 풀이

log n으로 문제를 해결하려면 Binary search를 해야합니다.

반으로 나눠서 탐색을 하겠다는 뜻으로 사전을 찾아볼때와 같이 탐색을 하는것입니다.

 

public int searchInsert(int[] nums, int target) {

        int l = 0;
        int r = nums.length-1;
        int mid = -1;
        while (l <= r) {
            mid = (l + r) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }

        return l;
    }

 

느낀점

O(n)과 O(logN)은 N이 커짐에따라 많은 차이가 납니다.

O(n)을 어떻게 O(logN)으로 줄일지에대한 고민을 많이 해봐야겠습니다.

 

참고

https://www.youtube.com/watch?v=Gzk4o07F18M