[LeetCode] 33. Search in Rotated Sorted Array

Search in Rotated Sorted Array - LeetCode

pivot을 기준으로 회전된 배열이 주어지고 target 이 주어집니다.

배열안에 target이 있다면 해당 인덱스를 반환하고

없다면 -1을 반환하는 문제입니다.

 

O(log n)안에 해결해야합니다.

 

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Example 3:

Input: nums = [1], target = 0
Output: -1

 

문제접근

O(log n)안에 풀어야 하지만 우선 완전탐색으로 접근했습니다.

 

데이터의 범위가 5000까지여서 O(n)의 시간복잡도가 필요한 코드도 통과가 되는것을 확인하였습니다.

    public int search(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            if (target == nums[i]) {
                return i;
            }
        }
        return -1;
    }

 

두번째 시도

O (log n) 시도

앞의 코드는 완전탐색으로 O(n)의 시간복잡도가 필요했습니다.

하지만 문제의 조건이 O(log n)이기 때문에 다른방식으로 접근해보겠습니다.

 

O(log n)의 시간복잡도를 갖는 알고리즘은 이분탐색이 있습니다.

하지만, 이분탐색은 정렬이 되어있는 배열이여야 합니다.

 

정렬을 해야하는데, 자바의 정렬 시간복잡도는 Dual Pivot Quick Sort를 사용하고 있으므로

O(n log n) 입니다.

 

그럼 정렬을 못사용한다는 뜻인데...

 

이때 그냥 데이터가 달라진 곳을 기준으로 두개를 나누어 이분탐색을 하면되지 않을까?

라는 생각이 떠올랐습니다.

데이터가 정렬이 아닌곳을 찾으면 되겠다는 생각을 하였습니다.

 

주의할점은 ret이 -1이 아니라면 이미 찾은것이니 이분탐색을 한번 더 하면 안되는 것입니다.

public int search(int[] nums, int target) {
        int pivot = -1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i-1] > nums[i]) {
                pivot = i-1;
            }
        }

        int ret = -1;
        ret = binarySearch(nums, target, 0, pivot);
        if (ret == -1) {
            ret = binarySearch(nums, target, pivot+1, nums.length-1);
        }
        return ret;
    }

    private static int binarySearch(final int[] nums, final int target, int left, int right) {
        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 -1;
    }

 

시간복잡도

pivot을 찾기위해 배열을 한번 반복하고 있습니다.

O(n)의 시간복잡도가 필요합니다.

 

O(n)...??

바보같이 첫번째 풀이에서 했던 for문을 사용했습니다...

배열을 둘로 나누기 전에 pivot된 위치를 찾을때 O(n)이 필요했던 것입니다...

O(log n)이 필요했기에 이번 시도는 실패입니다.

 

두번째 시도

이분탐색을 하면서 배열이 정렬된것을 확인하면서 target과의 관계를 확인하는 것입니다.

 

public int search(int[] nums, int target) {
        return binarySearch(nums, target, 0, nums.length-1);
    }

    private static int binarySearch(final int[] nums, final int target, int left, int right) {
        while (left <= right) {
            int mid = (left + right) / 2;

            if (nums[mid] == target) {
                return mid;
            }
            // 오른쪽은 정렬되어있는 상태
            if (nums[mid] <= nums[right]) {
                if (target > nums[mid] && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            } else { // 왼쪽 정렬된 상태
                if (target < nums[mid] && nums[left] <= target) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
        }
        return -1;
    }

시간복잡도

이분탐색을 사용하고있습니다.

O(log n)의 시간복잡도가 필요합니다.

 

느낀점

이분탐색은 조건설정을 잘 하면 정렬되어있지 않더라도 사용할 수 있다는것을 알게되었습니다.

 

참고

https://www.youtube.com/watch?v=vxLvYKDMexc