[LeetCode] Search in Rotated Sorted Array

문제설명

오름차순으로 정렬된 배열 Nums 가 있다.
이 배열 nums 의 k 번째 인덱스를 기준으로 자른다음에 두 도막의 위치를 맞바꾼다.
k 는 임의의 숫자이며, 문제에서는 이렇게 변환된 nums 배열이 input 으로 주어진다.
이때 nums 배열안에 target 이 몇번째 인덱스에 위치하고 있는지 알아내야한다.

단순히 반복문으로 O(N) 의 시간으로 해결할 수 있다.
하지만, 문제에서는 O(logN) 의 시간으로 해결하는 조건이 있다.

먼저 O(logN) 으로 해결하기 위해서는 이분탐색을 사용해야한다. 왜냐하면 내가 아는 탐색 알고리즘 중에 O(logN) 의 시간을 가지는 알고리즘은 이분탐색이 전부이기 때문이다.
하지만 문제는 이분탐색을 사용하기 위해서는 배열이 오름차순으로 정렬되어 있어야 하는데, nums 배열은 그렇지 않다. 오름차순으로 정렬된 두 도막으로 나뉘어져 있는 상태이다.

그럼 어떻게 오름차순으로 정렬할 수 있을까 ?

 

1) k 값을 찾아내서 합쳐져 있던 nums 도막을 두 도막으로 나눈다.
그럼 두 도막은 각각 오름차순이므로 각 도막에 이분탐색을 적용하면 될것이다.
하지만, 문제는 k 값을 찾아내기 위해서는 nums 배열에서 값이 감소하는 지점을 찾아야 하는데 그 지점을 찾을때까지 걸리는 시간이 O(N) 이므로 문제의 O(logN) 의 조건을 만족하지 못한다.

 

그럼, 어떻게 해야할까?....

O(logN) 의 시간안에 풀기 위해서는 배열을 조작하는 연산을 하면 안될것 같다는 생각이든다.
보통 배열 조작의 연산은 O(N) 이기 때문이다.

그럼 배열에 바로 이분탐색을 적용할 수 있는 방법이 있을까 ?..

내가 생각해낸 방법은 케이스별로 나누는 것이다.

1) tartget >= start 일땐, 이분탐색을 해야하는 범위는 왼쪽 도막이다.

2) finish < target < start 일땐, target은 nums 배열안에 존재하지 않는다.

3) target <= finish 일땐, 이분탐색을 해야하는 범위는 오른쪽 도막이다.

이제 왼쪽도막과 오른쪽 도막을 탐색하는 방법을 생각해야하는데 nums 배열의 0, n-1 번째 인덱스의 값과 mid 의 값을 비교하면 간단하게 할 수 있다.

만약 왼쪽 도막을 탐색해야 하는 상황이고, nums[mid] < nums[0] 이면 현재 mid 는 오른쪽 도막에 위치하고 있다는 소리니깐, high = mid - 1 로 바꿔주면 된다.

반대로 오른쪽 도막을 탐색해야하는 상황이고 nums[mid] > nums[-1] 이면 현재 mid 는 왼쪽 도막에 위치하고 있다는 소리니깐 low = mid + 1 로 바꿔주면 된다.

이 과정은 처음 딱 1번만 진행하게 되고, 도막이 정확히 정해진 이후부터는 정확한 이진탐색이 시작된다.

풀이_#1 O(N)

class Solution:
    def search(self, nums: List[int], target: int) -> int:

        for i in range(len(nums)):
            if (nums[i] == target):
                return i

        return -1

풀이_#2 O(logN)

class Solution:
    def search(self, nums: List[int], target: int) -> int:

        start = nums[0]
        finish = nums[-1]

        n = len(nums)

        if (n == 1):
            if (start == target):
                return 0
            else:
                return -1


        low = 0
        high = n - 1

        if (start <= target):
            loc = "Left"
        elif (finish < target < start):
            return -1
        else:
            loc = "Right"

        while (low <= high):
            mid = low + (high - low)// 2
            if (nums[mid] == target):
                return mid

            if (loc == "Left" and nums[mid] < nums[0]):
                high = mid - 1
                continue

            if (loc == "Right" and nums[mid] > nums[-1]):
                low = mid + 1
                continue

            if (nums[mid] < target):
                low = mid + 1
            else:
                high = mid - 1

        return -1