[Java] 35. Search Insert Position

문제 파악

중복되지 않는, 정렬된 정수 배열이 주어진다.

 

target 에 해당하는 원소의 위치나, 없다면 삽입했을때 정렬을 유지할 수 있는 인덱스의 위치를 반환해야한다.

 

그리고 시간 복잡도는 O(logN) 이어야 한다.

 

---

풀이

1️⃣ 이분 탐색

💡 떠오른 Idea

시간 복잡도를 O(logN) 으로 해야한다는 말을 보자마자, 이분탐색으로 해결해야겠구나 생각이 들었다.

이분탐색을 구현해서, target 이 들어갈 수 있는 적절한 위치를 찾으면 된다.

 

nums가 정렬되어있기 때문에

 

target이 nums의 어떠한 원소보다 작거나 큰 경우는 앞선에서 처리해주었다.

 

이분탐색에서는, 정렬을 유지하면서 target 값 이하를 배열에 입력할 수 있는 인덱스를 반환하도록 구성하였다.

 

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

        if (target < nums[0]) {
            return 0;
        } else if (target > nums[nums.length - 1]) {
            return nums.length;
        }

        int left = 0, right = nums.length - 1;

        while (left < right) {
            int mid = (left + right) / 2;
            if (target <= nums[mid]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

 

결과

 

---

📖 회고

예전에 많이 연습해보았던 이분 탐색의 가장 기초적인 문제라서 쉽게 해결할 수 있었다.

 

기본 문제를 풀어보면서, 이분탐색의 원리를 다시 생각해 볼 수 있어서 좋은 시간이었다.