[LeetCode 풀이/python] 81. Search in Rotated Sorted Array II (medium)

문제 설명: 정수 배열 nums 는 오름차순 정렬되어 있다 (항상 구분되는 distinct 값들로만 구성된 것은 아님). 네가 작성한 함수를 통과하기 전, 배열 nums 는 알려지지 않은 피벗 인덱스 k (0 <= k < nums.length) 를 기준으로 회전되어 rotated, 결과적으로 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed) 의 배열이 된다. 예를 들어, 배열 [0,1,2,4,4,4,5,6,6,7] 는 피벗 인덱스 5 에서 회전될 경우 [4,5,6,6,7,0,1,2,4,4] 가 된다. 회전 후의 배열 nums 와 정수 target 이 주어졌을 때, 해당 정수 target 이 배열 nums 에 존재하면 true 를, 존재하지 않으면 false 를 리턴하시오.

 

(There is an integer array nums sorted in non-decreasing order (not necessarily with distinct values).

Before being passed to your function, nums is rotated at an unknown pivot index k (0 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,4,4,5,6,6,7] might be rotated at pivot index 5 and become [4,5,6,6,7,0,1,2,4,4].

Given the array nums after the rotation and an integer target, return true if target is in nums, or false if it is not in nums.)

 

예시 1)

입력: nums = [2,5,6,0,0,1,2], target = 0  -->  출력: true

 

예시 2)

입력: nums = [2,5,6,0,0,1,2], target = 3 -->  출력: false

 

제한 조건:

• 1 <= nums.length <= 5000
• -10^4 <= nums[i] <= 10^4
• nums is guaranteed to be rotated at some pivot.
• -10^4 <= target <= 10^4

 

 

 

------ * ------ * ------ * ------

 

[풀이 1안]  

• 접근법
  • 기본적으로 정렬된 배열을 회전한 것이므로 이진 탐색(binary search) 을 활용하여 탐색하되, 탐색 범위를 줄여 나가는 조건 설정에 있어서 회전(rotation) 상황을 추가적으로 고려해야 함
  • 회전된 배열 입력 nums 에 대해 일단 left, right, middle (이하 l, r, mid) 에 해당하는 요소를 확인할 경우,
    • 일단 1) target == nums[mid] 인 경우 타겟을 찾았으므로 탐색 종료
    • 그렇지 않으면, 2) nums[mid] <= nums[r] <= nums[l]  또는  3) nums[r] <= nums[l] <= nums[mid]  의 경우가 가능함
    • 2) 의 경우는 k <= mid  로서 mid ~ r  사이에 해당하는 범위는 반드시 오름차순 정렬되어 있음*
    • 3) 의 경우는 k > mid 로서 l ~ mid 사이에 해당하는 범위가 반드시 오름차순 정렬되어 있음*
  • 2), 3) 을 r 과 mid 의 관계를 중심으로 다시 세분화 하면,
    • nums[mid] < nums[r] : target 이 정렬된 범위인 mid < target <= r  사이에 존재할 경우 일반적인 이진탐색과 같이 mid+1 이 새로운 l 이 되도록 범위를 좁히고, 그렇지 않은 경우 나머지 범위에 대해 탐색함
    • nums[mid] > nums[r] : target 이 정렬된 범위인 l <= target < mid 사이에 존재할 경우, 마찬가지로 mid-1 이 새로운 r 이 되도록 탐색 범위를 좁히고, 그렇지 않은 경우 나머지 범위에 대해 탐색
    • nums[mid] == nums[r] : mid ~ r 범위가 모두 동일한 값을 가질 것이므로 r 인덱스를 1씩 앞으로 당겨 mid 값을 재조정함

 

• 코드 구현

def search(nums: List[int], target: int) -> bool:
    l, r = 0, len(nums)-1
    while l < r:
        mid = l + (r-l)//2

        if target == nums[mid]:
            return True
        elif nums[mid] < nums[r]:
            if nums[mid] < target <= nums[r]: l = mid+1
            else: r = mid-1
        elif nums[mid] > nums[r]:
            if nums[l] <= target < nums[mid]: r = mid-1
            else: l = mid+1
        else:
            r -= 1
                
    if nums[l+(r-l)//2] == target: return True
    else: return False

 

• 결과
  • 동일한 문제 시리즈의 I (33번 문제) 에서는 이진탐색을 두 번 써서 (피벗 인덱스 k 찾기 & 정렬 상태로 원복 후 이진탐색 적용) 풀었는데, 본 문제는 배열 내 중복된 값이 존재하여 해당 접근법으로 풀 수 없었음...
  • nums[l], nums[r], nums[mid] 의 값이 동일한 경우들이 존재하다 보니 조건 설정에 있어 까다로운 면이 있는 듯
  • mid 와 r 의 관계로만 정리하고 nuns[mid] == nums[r] 인 경우 r -= 1 을 해주는 것이 제일 생각하기 어려웠던 부분...!
  • 이진탐색 구현 일반에 있어 mid = l + (r-l)//2 로 구하는 것도 성능 향상에 도움 된다고! (overflow 가 업스스..)