Java, LeetCode | 35. Search Insert Position

🚀 풀이 후기

이진 탐색 문제를 오랜만에 푸니까 요령이 생겼습니다.

항상 헷갈렸던 부분이 else if 구문에서 어느 조건에 answer 답변을 세팅해줘야 하는지였습니다.

아래 문제에서 Example 2를 보면 nums[i] < target < nums[i+1] 일 때 answer = i+1 을 넣어주므로, 

코드를 짤 때, target <  nums[i] 인 조건에서 answer = i 를 세팅해주면 됩니다.

 🌒 문제 설명

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 <= 104
-104 <= nums[i] <= 104
nums contains distinct values sorted in ascending order.
-104 <= target <= 104

🌓 문제 풀이

위 문제는 이진 탐색(Binary Search) 문제입니다.

 

이진탐색은 정렬돼 있는 데이터에서 특정 값을 찾아내는 알고리즘입니다.

탐색 범위를 반으로 줄여가며 O(long n) 시간복잡도가 나옵니다.

리트코드 Example1, Example2 풀이

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0; // nums 배열의 가장 작은 index
        int right = nums.length - 1; // nums 배열의 가장 큰 index
        int answer = 0; // 리턴할 답
        while (left <= right) { // 이분 탐색을 하는 조건
            int mid = (left + right) / 2; // 이분 탐색할 index
            if (nums[mid] == target) { // 탐색한 값이 target 이라면 답 저장 후 break
                answer = mid;
                break;
            } else if (nums[mid] > target) { // 탐색한 값이 target 보다 크다면 탐색 범위를 작게 만듭니다.
                answer = mid; // 배열에 target 값이 없을 수 있으므로 예비 정답을 저장합니다.
                right = mid - 1;
            } else { // 탐색한 값이 target보다 작다면 탐색 범위를 크게 만듭니다.
                left = mid + 1;
            }
        }
        
        // nums배열의 마지막 값이 target보다 작다면,
        // 답은 배열의 마지막 index 보다 1 커야 하므로 배열의 길이를 저장합니다.
        if (nums[nums.length - 1] < target) {  
            answer = nums.length;
        }

        return answer;
    }
}

🌕 리팩토링

target 값이 nums 배열에 없는 경우 left를 반환하면 됩니다.

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

 

---

리트코드 문제

깃허브 코드