LeetCode-33 Search in Rotated Sorted Array 파이썬 풀이

Search in Rotated Sorted Array - LeetCode

문제

오름 차순으로 정렬된 int형 배열 nums가 있습니다. nums가 특정 수만큼 회전했다고 가정했을 때 다시 몇번을 회전 시켜야 target에 해당하는 요소를 마주칠 수 있는지 반환하는 문제입니다. 만약 target이 배열안에 존재하지 않는다면 -1을 반환하면 됩니다.

풀이

nums를 회전 시키는 수는 현재 위치한 target의 인덱스 수와 동일하기 때문에 파이썬에선 index를 활용해 쉽게 해결할 수 있습니다. if not in을 활용하여 target이 없는 경우 -1 을 반환하도록 하면 문제 없이 실행 됩니다.

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if target not in nums:
            return -1
        else:
            return nums.index(target)
        

다른 방법은 이진 탐색을 통해 target 값을 찾는 방법입니다. 이때 주의해야 할 점은 주어진 nums가 오름차순으로 정렬되어 특정 수만큼 회전했다는 것 입니다. 

1. 이진 탐색을 수행하며 만약 중간값이 찾으려는 값과 같다면 중간값(인덱스)를 반환합니다.

2. 배열의 left(가장 처음값)가 mid(중간 값)보다 작거나 같다면 left ~ mid까지는 오름차순으로 정렬되어 있는 것 입니다.

3. 만약 이때 target이 left보다 작다면 target은 mid 이후에 존재할 것 입니다. (target < left <= mid ) 따라서 target이 left보다 작다면 left를 mid 다음 값으로 지정해 줍니다. target이 mid보다 큰 경우도 마찬가지 입니다. mid 값 보다 left가 작기 때문에 당연히 target은 mid보다 뒤에 위치해 있습니다.( left <= mid < target) 이후 1로 돌아가 반복합니다. 

4. 만약 left가 mid보다 크다면 이 사이에 배열의 시작점이 존재할 것 입니다.

5. 이때 target이 mid보다 작다면 target은 left ~ mid-1 사이에 존재할 것이기에 right를 mid -1로 설정하고 1로 돌아가 반복합니다. target이 right 보다 큰 경우도 마찬가지 입니다. 현재의 경우가 left 와 mid 사이에 배열의 시작점이 존재하는 경우이기 때문에 right값보다 left가 클수 있습니다.

6. 이 반대의 경우에는 mid +1 ~ right 사이에 target이 존재하는 경우이기 때문에 left를 mid +1로 설정하고 1로 돌아가 반복합니다. 

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums)-1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                return mid

            if nums[left] <= nums[mid]:
                if nums[mid] < target or target < nums[left]:
                    left = mid + 1
                else:
                    right = mid - 1
            else:
                if target < nums[mid] or target > nums[right]:
                    right = mid - 1
                else:
                    left = mid + 1
        return -1