[NeetCode/Python] Find Target in Rotated Sorted Array

문제 링크: https://neetcode.io/problems/find-target-in-rotated-sorted-array

NeetCode

 

굉장히 특이한 문제였다.

O(n)으로 하면 풀기 쉽지만 O(log n)의 시간 복잡도로 문제를 풀라고 되어있다.

딱 보자마자 binary search가 떠올랐는데 문제는 문제 조건이다. binary search는 알다시피 정렬된 배열에서 사용하는 sort 알고리즘이다.

하지만 이 문제는 기존 정렬 배열에서 특정 횟수만큼 rotate된 배열을 input으로 두었다.

binary search를 활용하여 푸는 문제들은 봤어도 이렇게 응용한 문제는 처음봐서 굉장히 신선했다.

---

- 풀이 찾아 해매기

1. 

처음에는 기존 sorted array에서 rotate가 된거니 rotate된 횟수를 알면 binary search를 사용할 수 있겠다고 생각했다.

왜냐하면 rotate된 횟수로 기존 array 의 index를 이용하여 binary seach 알고리즘을 그대로 적용할 수 있기 때문이다.

result = (original index + rotate times) % 6	# rotate 된 index
reserse = (length - rotate times) % 6	# rotate 되기 전 index(?)를 구하려고 했던듯

 

그런데 이 문제의 똑똑한 점은 rotate 횟수를 알려주지 않는다는 점이다!!

 

2.

고민하다가 솔직히 풀이과정 동영상을 앞부분만 봤다. (멩세코 전체를 보지 않았다! 힌트만 얻으려고 했음)

 

동영상에서 아주 신박하게 이 배열을 차트로 그려낸걸보고 바로 유레카를 외치며 동영상을 다 보지 않았다!

와.. 이렇게 간단하고 보기 쉽게 이 문제를 그림으로 그려내다니 다시 한번 너무 놀라웠다.

 

저렇게 그래프를 그리면 이 문제의 케이스들을 분류할 수 있게 된다.

총 4가지가 있다.

(이 케이스들은 아이패드로 그려서 나중에 첨부하겠다)

 

케이스별로 구분이 되어야 binary seach 알고리즘을 활용할 수 있다.

그렇다면 이 케이스들을 어떻게 구분할 수 있을까? 우리가 알고 있는 값은 mid와 left, right 값, 그리고 target 값이다.

이 정보들로 충분히 케이스들을 구분할 수 있고 그 코드는 아래와 같다.

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1

        while (left <= right):
            mid = (left + right) // 2

            if nums[mid] == target:
                return mid

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

        return -1

 

정말 많은걸 배운 문제였다.

 

시간 복잡도

배열 길이 : N

=> O(log N)