Search in Rotated Sorted Array | LeetCode 804 | Python3 🐍

 

📄 목차

 

 

🤔 문제 : Search in Rotated Sorted Array | LeetCode 804

문제: https://leetcode.com/explore/interview/card/top-interview-questions-medium/110/sorting-and-searching/804/

정렬된 배열에서 타겟 숫자의 인덱스를 찾는 문제입니다.

단, 여기서 배열은 rotated 되어있습니다.

예를들어,

[0,1,2,4,5,6,7]

배열을 오른쪽으로 4칸 옮겨 

[4,5,6,7,0,1,2]

를 만드는 식입니다.

 

 

💡 풀이

1. Rotate 된 시작점을 찾은 후 한쪽 범위에서 BS

가장 먼저 떠올린 풀이는 어느부분부터 Rotate된 것인지, pivot을 찾자는 거였습니다.

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

이 케이스의 경우 7과 0 사이가 rotate 된 거겠죠? 

그 값을 기준으로 배열을 둘로 나눕니다. 

1) [ 4, 5, 6, 7 ]

2) [ 0, 1, 2 ]

 

각각의 배열은 잘 정렬된 배열이니 Binary Search를 쓸 수 있죠. 

둘 중 타겟을 포함하는 범위인 2) 배열에 대해서 Binary Search를 적용하여 타겟값 인덱스를 찾으면 됩니다.  

 

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if not nums: return -1
        if len(nums) == 1: return 0 if target == nums[0] else -1
        def bsPivot(st, ed):  # rotated 지점을 찾기 위한 Binary Search 
            md = int((st+ed)/2)
            if nums[md] > nums[md+1] : return md
            if nums[md] >= nums[st]: return bsPivot(md+1, ed)
            return bsPivot(st, md-1)
        def bs(st, ed):  # 타겟을 찾기 위한 Binary Search
            # print("bs", st, ed)
            if st > ed: return -1
            md = int((st+ed)/2)
            if nums[md] == target: return md
            if nums[md] > target: return bs(st, md-1)
            return bs(md+1, ed)
        pivot = len(nums)-1 if nums[-1] > nums[0] else bsPivot(0, len(nums)-1)
        # print(pivot)
        if nums[0] <= target: return bs(0, pivot)
        else: return bs(pivot+1, len(nums)-1)

 

Time Complexity
logN(pivot찾기) + logN
O(logN)

 

성능이 무척 별로네요.. 아무래도 더 좋은 풀이가 있나봅니다.

 

2. BS를 바로 적용할 수 있는 방법이 있을까?

첫번째 풀이는 아무래도 배열을 한 번 순회하며 rotate 지점을 찾아야 하니 n이 소요됩니다.

(rorate지점을 binary search로 찾을수도 있지만.. 오히려 연산이 복잡하여 더 느리더라구요)

 

rotate지점을 찾지 않고 바로 BS를 적용할 수 있는 로직이 있을까요?

 

BS의 특징은 주어진 배열의 범위를 반씩 줄여가며 타겟값을 찾는것입니다.

rotated 배열의 경우 범위를 반으로 나눠 배열 두개로 만들면, 

1) 잘 정렬된 배열 -  첫값이 마지막값보다 작음

2) rotated 배열 - 첫 값이 마지막값보다 큼

이렇게 나눠지게 됩니다. 

[ 4, 5, 6, 7, 0, 1, 2 ]
[ 4, 5, 6] [7, 0, 1, 2]
     X     [7, 0][1, 2]
              0     X

1) 배열에서 타겟 범위를 포함할 가능성이 있는지는 간단히 확인할 수 있죠?

1) 배열이 타겟 범위를 포함한다면 1)에 대해 BS를 수행하고

그렇지 않다면 2)에 대해 BS를 수행하는 방식으로 하면 되겠네요. 

 

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if not nums: return -1
        if len(nums) == 1: return 0 if target == nums[0] else -1
        def bs(st, ed):
            # print(st, ed)
            if st > ed: return -1

            md = int((st+ed)/2)
            if nums[md] == target: return md

            # 왼쪽은 바르게 정렬됨
            if nums[md] >= nums[st]:
                if nums[st] <= target <= nums[md]: return bs(st, md-1)
                else: return bs(md+1, ed)
            # 오른쪽은 바르게 정렬됨
            else:
                if nums[md] <= target <= nums[ed]: return bs(md+1, ed)
                else: return bs(st, md-1)

        return bs(0, len(nums)-1)

 

Time Complexity
O(logN)