[Leetcode] 153. Find Minimum in Rotated Sorted Array (python)

#1.  문제

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/

Find Minimum in Rotated Sorted Array - LeetCode

 

 

정렬된 정수 배열 nums가 1 부터 n번까지 순회한 상태 (옆으로 한칸씩 이동)라고 가정할 때, 최솟값을 찾는 문제

풀이는 O(logN)으로 풀이해야 한다.

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

Output: 
0

Explanation:
[0, 1, 2, 4, 5, 6]의 초기 배열이 4번 이동하여 [4,5,6,7,0,1,2]으로 변화

 

 

---

#2.  풀이

 

다른 풀이 방법을 고려하지 않고, 처음 생각에 매몰되어 결국 케이스 통과가 실패한 풀이

class Solution:
    def findMin(self, nums: List[int]) -> int:
        def search(left: int, right: int):

            mid = (left + right) // 2

            if left == right:
                return nums[0]

            if nums[mid] > nums[mid + 1]:
                return nums[mid + 1]
            elif nums[mid] < nums[mid + 1]:
                return search(mid + 1, right)
            else:
                return search(left, mid - 1)

        left, right = 0, len(nums) - 1

        return search(left, right)

 

별로 어렵지 않다고 생각했던 문제여서, 더 나은 방법을 고민하기 힘들었다.

이진탐색과 재귀를 이용해서 풀었는데, 아직도 충분히 최적화가 가능하다고 생각한다.

재귀를 이용한 더 쉬운 풀이가 있지만 문제 요구사항인 O(logN) 풀이에 위배된다.

 

솔루션을 참고한 풀이

class Solution:
    def findMin(self, nums: List[int]) -> int:

        left, right = 0, len(nums) - 1
        min_num = nums[0]

        while left <= right:

            if nums[left] < nums[right]:
                min_num = min(min_num, nums[left])
                break

            mid = (left + right) // 2
            min_num = min(min_num, nums[mid])

            if nums[mid] >= nums[left]:
                left = mid + 1
            else:
                right = mid - 1

        return min_num

문제의 핵심과 패턴을 다르게 생각하고 있던 것이 패착이었다.

오름차순 정렬과 오른쪽으로 한칸씩 이동한다는 것을 잘 생각해보면 쉽게 풀 수도 있었을 것 같은 아쉬운 문제.

 nums[mid] >= nums[left] 인 경우 오른쪽 배열에서 최솟값을 찾고, 반대의 경우 왼쪽 배열에 최솟값이 있으므로 왼쪽을 찾는다.
nums[left]와 비교를 하는 이유는 배열은 정렬된 상태이므로 nums[left]는 mid 기준 무조건 왼쪽 배열의 최솟값이기 때문이다.
ex) nums = [3, 4, 5, 1, 2], nums[mid] = 5 >= nums[left] = 3 이고, 즉 nums[left:mid+1] = [3,4,5] 이기 때문에 왼쪽은 찾을 필요가 없다.
이 과정에서 min값을 계속 갱신한다.