[LeetCode] - 35. Search Insert Position

LeetCode는 프로그래밍 문제를 풀며 코딩 실력을 향상할 수 있는 온라인 플랫폼입니다. 다양한 알고리즘 및 데이터 구조 문제를 제공하며, 면접 대비에 유용합니다. 해당 문제는, LeetCode Problems에서 볼 수 있는 난이도 '쉬움 (Easy)' 단계인 "Search Insert Position" 문제입니다.

--> https://leetcode.com/problems/search-insert-position/description/

 

문제 : 

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You must write an algorithm with O(log n) runtime complexity.

---

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

 

Constraints :

• 1 <= nums.length <= 10^4
• -10^4 <= nums[i] <= 10^4
• nums contains distinct values sorted in ascending order.
• -10^4 <= target <= 10^4

---

이 문제는 주어진 정렬된 배열에서 목푯 값을 찾고, 목푯 값이 존재하면 그 인덱스를 반환합니다. 목푯 값이 존재하지 않으면, 정렬 순서를 유지하면서 삽입될 위치의 인덱스를 반환합니다. 또한, 이 알고리즘은 O(log n) 시간 복잡도를 가져야 합니다.

바로 제 코드를 보시겠습니다 : 

class Solution {
    public int searchInsert(int[] nums, int target) {
        int res = 0;
        List<Integer> numsArr = new ArrayList<>();
        for (int num : nums) {
            numsArr.add(num);
        }

        if (numsArr.contains(target)) {
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] == target) {
                    res = i;
                }
            }
        } else {
            numsArr.add(target);
            Collections.sort(numsArr);
            for (int i = 0; i < numsArr.size(); i++) {
                if (numsArr.get(i) == target) {
                    res = i;
                }
            }
        }

        return res;
    }
}

 

코드를 단계별로 설명해드리겠습니다 : 

1. 리스트 초기화:
   • nums 배열의 요소를 numsArr 리스트에 복사합니다.
2. 목푯 값이 존재하는 경우:
   • numsArr에 목푯 값이 포함되어 있는지 확인합니다.
   • 목표목푯 값이 포함되어 있으면, 배열을 순회하며 목푯 값의 인덱스를 찾습니다.
3. 목푯
   • 값이 포함되어 있지 않으면, 리스트에 목표 값을 추가합니다.
   • 리스트를 정렬합니다.
   • 정렬된 리스트를 순회하며 목표 값의 인덱스를 찾습니다.
4. 끝.

눈치채셨는지는 모르겠지만, 이 코드는 O(logn)이 아닙니다. 

시간 복잡도 분석을 하자면 :

1. 리스트 초기화 :
   • 배열을 리스트로 복사하는 데 O(n)의 시간이 걸립니다.
2. 목표 값 존재 여부 확인 :
   • numsArr.contains(target)는 리스트를 순회하며 목표 값을 찾으므로 O(n)의 시간이 걸립니다.
   • 목표 값이 리스트에 있는 경우, 배열을 순회하며 인덱스를 찾는 데 O(n)의 시간이 걸립니다.
3. 목표 값이 존재하지 않는 경우 :
   • numsArr.add(target)는 O(1)의 시간이 걸립니다.
   • Collections.sort(numsArr)는 O(n log n)의 시간이 걸립니다.
   • 정렬된 리스트를 순회하며 인덱스를 찾는 데 O(n)의 시간이 걸립니다.

따라서 최종 시간 복잡도는 O(n log n)입니다. 이는 주어진 문제의 요구 사항인 O(log n) 시간 복잡도를 만족하지 않습니다.

알고리즘 수업을 듣고 나서야 이 코드를 개선할 수 있게 되었는데요, 바로 이진 탐색을 쓰는 겁니다.

---

개선된 코드 : 

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
}

 

이진 탐색을 사용한 위 코드의 시간 복잡도는 O(log n)으로, 주어진 문제의 요구 사항을 충족합니다.

---

개선되기 전 후 코드들의 Runtime 결