LeetCode 35(Search Insert Position, java)

0. 문제

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

Search Insert Position - LeetCode

 

1. 문제 설명

- 문제에서 중복이 없는 정수형 배열(nums)과 찾는 수(target)가 주어진다.

- 배열을 탐색하면서 target이 존재한다면 target의 index를 반환한다. 

- 만약 target이 없다면 target이 있어야 하는 위치의 index를 반환한다.

- 이 문제는 O(log n)의 시간 복잡도로 탐색하는 것이 문제의 핵심이다. 

 

2. 문제 해설

a) 첫 번째 접근

- O(log n)의 시간 복잡도를 구현하기 위해서 이진 탐색을 이용한다.

- 이진 탐색의 효율을 극대화시키기 위해서 two pointers 방법을 사용한다.

 

- 두 포인터는 다음과 같이 설정한다.

   → 배열의 첫 번째 원소의 위치를 start

   → 마지막 원소의 위치를 end

 

b) 두 번째 접근

- target이 존재한다면 target의 index를 반환하면 되지만, 문제는 target이 존재하지 않는 경우다.

- target이 존재하지 않는 경우, target이 들어갈 수 있는 위치를 찾아야 한다.

- 그러므로 반복문은 start와 end가 동일할 때 종료될 수 있도록 한다. 

- 그 이유는 다음과 같다. 

 

   1) target이 배열에 존재하지 않고, 배열의 요소보다 큰 숫자인 경우

    → target이 배열의 모든 요소보다 큰 숫자인 경우, start는 계속해서 증가한다.

    → start는 end와 동일한 값을 가질 때까지 증가한다. 

    → 이를 기반으로 mid를 계산하면, 가장 마지막 원소의 index를 가지게 되고 반복문은 종료한다. 

    → target이 nums[mid]보다 큰 경우, mid + 1을 반환하면 된다. (target이 가장 큰 수이기 때문)

    → target이 nums[mid]보다 작은 경우, mid를 반환하면 된다. (target이 마지막 원소보다 작기 때문)

 

   2) target이 배열에 존재하지 않고, 배열의 요소보다 작은 숫자인 경우

    → target이 배열의 모든 요소보다 작은 숫자인 경우, end는 계속해서 감소한다.

    → end는 start와 동일한 값을 가질 때까지 감소한다. 

    → 이를 기반으로 mid를 계산하면, 첫 번째 원소의 index(= 0)를 가지게 되고 반복문은 종료한다. 

    → target이 nums[mid]보다 큰 경우, mid + 1을 반환하면 된다. (target이 첫번째 원소보다 크기 때문)

    → target이 nums[mid]보다 작은 경우, mid를 반환하면 된다. (target이 가장 작은 수이기 때문)

 

   3) target이 배열에 존재하지 않고, 배열 내부의 어느 요소보다 작거나 큰 경우

    → target이 존재하지 않으므로 start와 end는 계속해서 증감하게 된다. 

    → start가 증가하거나 end가 감소하는 연산을 반복해서 수행하게 된다.

    → 어느 순간 start와 end가 동일한 값을 가지는 경우가 발생하게 된다.

    → 이를 기반으로 mid를 계산하면, target이 존재할 수 있는 위치를 반환하게 된다.   

    → target이 nums[mid]보다 큰 경우, mid + 1을 반환하면 된다. (target이 해당 원소보다 크기 때문)

    → target이 nums[mid]보다 작은 경우, mid를 반환하면 된다. (target이 해당 원소보다 작기 때문)

 

- 다음 코드를 보면서 이해해보자. 

 

3. 정답 코드

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