리트코드 - 35. Search Insert Position

리트코드 - 35. Search Insert Position

출처 - https://leetcode.com/problems/search-insert-position/description/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

중복되지 않는 정수로 이루어진 정렬된 배열과 목표 값이 주어질 때,
목표 값이 발견되면 해당 인덱스를 반환하고 발견되지 않으면 목표 값을 배열에 삽입하려면 어느 인덱스에 삽입해야 하는지 인덱스를 반환합니다.

O(log n) 런타임 복잡도를 가지는 알고리즘을 작성해야 합니다.

 

의사코드

left = 0 right = nums.length - 1 mid = 0 반복문 시작 (left <= right)     mid = left + (right-left) / 2     if (nums[mid] == target)         mid 리턴     if (nums[mid] < target)         left = mid -1     if (nums[mid] > target)         right = mid + 1 반복문 종료 left 리턴

 

풀이코드

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int mid = 0;

        while (left <= right) {
            mid = left + (right - left) / 2;

            if (nums[mid] == target) {
                return mid;
            } 
            if (nums[mid] < target) {
                left = mid + 1;
            } 
            if (nums[mid] > target) {
                right = mid - 1;
            }
        }
        return left;
    }
}

 

코드설명

문제에서 O(log n)만큼의 시간복잡도를 가지라 했으니 이진탐색이 가장 적합한 방법이다.

투 포인터를 이용해서 왼쪽과 오른쪽의 중간값(mid)을 기준으로 target과 비교한다.

 

target보다 배열의 mid번째 값이 작다면 왼쪽을 탐색해야 하므로 right=mid - 1을 하고

mid번째 값이 크다면 오른쪽을 탐색해야 하므로 left = mid + 1을 한다.

만약 target과 일치하는 값이 나온다면 이때의 인덱스를 리턴하면된다.

 

하지만 동일한 값이 아닐 경우에는 left를 리턴하면 되는데 이는 아래 예제를 통해 자세하게 설명한다.

예시 1

먼저 이런 크기 4짜리 배열이 있고, target이 2라면 left와 right의 중간값인 mid는 1이 된다.

3 > 2 이므로 왼쪽을 탐색해야 해서 right = mid - 1 = 0이된다.

다시 left와 right의 중간값인 mid는 0이 되고 이 때 0 < 2 이므로 left = mid + 1 = 1 이 된다.

left 가 right보다 커졌으므로 반복문을 빠져나오고 이때의 left값이 들어가야 하는 인덱스가 된다.

 

예시2

target이 8인 경우는 어떨까?

위와같이 left가 right보다 커지면서 빠져나오고 left값이 들어가야 하는 인덱스가 된다.

 

즉, 값이 일치하는 경우는 mid, 아닌 경우는 left를 통해서 확인할 수 있다.

 

시간복잡도 - O(log n)

공간복잡도 - O(1)

 

문제를 풀며 생각한 흐름과 배운 점

설명에는 매우 쉽게(?) 설명했지만 은근히 이진탐색에서 인덱스 문제 때문에 골머리를 앓았다.

mid로 모든 것을 해결하려고 하다가 자꾸 어떤 데는 적용이 안되고 어떤데는 되길래 메모장에 그려가면서 로직을 이해하려고 해봤다.

이진 탐색이 돌아가는 원리를 익히는 좋은 기회가 되었다.

 

정리

이진탐색과 투포인터를 이용한 배열 순회 방법