[LeetCode 풀이/python] 154. Find Minimum in Rotated Sorted Array II (hard)

문제 설명: 크기 n 의 오름차순 정렬된 배열 nums 가 1 에서 n 사이의 횟수만큼 회전되어 있다. 예를 들어, 배열 nums = [0,1,4,4,5,6,7] 은 다음과 같이 될 수 있다:

• 4 번 회전할 경우 [4,5,6,7,0,1,4] 
• 7 번 회전할 경우 [0,1,4,4,5,6,7]

배열 [a[0], a[1], a[2], ..., a[n-1]] 을 한 번 회전한 결과는 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 와 같다. 정렬되어 회전된 배열 nums 가 주어졌을 때, 해당 배열이 중복(duplicates) 을 포함할 경우, 해당 배열에서 가장 작은 원소를 찾아 리턴하시오.

 

(Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,4,4,5,6,7] might become:

• [4,5,6,7,0,1,4] if it was rotated 4 times.
• [0,1,4,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums that may contain duplicates, return the minimum element of this array.)

 

 

예시 1)

입력: nums = [1,3,5]  -->  출력: 1

 

예시 2)

입력: nums = [2,2,2,0,1]  -->  출력: 0

 

제한 조건:

• n == nums.length
• 1 <= n <= 5000
• -5000 <= nums[i] <= 5000
• nums 는 정렬되어 있고 1 ~ n 사이의 횟수만큼 회전되어 있다

 

 

 

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

 

[풀이 1안]

• 접근법
  • 유일한(unique) 원소들로만 배열이 구성된 문제 153 (Find Minumum ~ I) 과 달리, 중복된 값이 있어서 조건문 설정이 좀더 까다로운 편!
  • 회전 이전에 정렬되어 있는 배열이므로 기본적으로 이진 탐색(binary search) 을 이용하되, l / m / r 에 해당하는 값들의 대소 관계에 따라 다음 탐색 범위를 다르게 설정
    • l <= m < r  이면 회전 후에도 정렬 결과가 꼬이지 않은 상태이므로 l 에 해당하는 원소가 최소값을 갖게 됨
      ( l 과 m 사이에만 = 관계가 허용됨이 포인트...! )
    • 해당 경우가 아닌 경우, 정렬 관계가 꼬여 있음 -->  최소값이 존재할 수 있는 범위로 이진 탐색을 통해 l, r 의 인덱스 차이가 1이 될 때까지 범위를 좁혀 나간 뒤, 둘 중 min 값을 리턴
    • m > r 인 경우, m 이후 인덱스에 최소 값이 존재하게 되므로, m 을 새로운 l 으로 설정
    • l > m 인 경우, m 이전 인덱스에 최소 값이 존재하게 되므로, m 을 새로운 r 으로 설정
    • m == r 인 경우,  m ~ r 범위는 모두 같은 값을 갖고 있을 것이므로 r 을 한 칸씩 m 까지 당겨옴

 

• 코드 구현

def findMin(nums: List[int]) -> int:
    l, r = 0, len(nums)-1
    if len(nums) == 1:
        return nums[0]
        
    while l < r:
        m = l + (r-l)//2
        if nums[l] <= nums[m] < nums[r]:
            return nums[l]
            
        if r - l == 1:
            return min(nums[r], nums[l])
            
        elif nums[m] == nums[r]:
            r -= 1
        elif nums[m] > nums[r]:
            l = m
        else:
        #elif nums[l] > nums[m]:
            r = m

 

• 결과
  • 기본적으로 이진 탐색을 이용하므로 O(log n) 의 시간 복잡도 가짐~
  • 따로 풀이 참고 안하고 풀어서 뿌듯 ~_~