📕문제

[LeetCode] 153. Find Minimum in Rotated Sorted Array

문제 설명

1에서 n번만큼 회전된 길이가 n인 정렬된 리스트가 주어졌을 때 가장 작은 수를 출력하는 문제다.
이 때 회전이란 [0, 1, 2] 가 있을 때 1번 회전하면 [2, 0, 1], 2번 회전하면 [1, 2, 0]이 된다.
시간복잡도 $O(logN)$ 안에 해결해야 한다.

---

📝풀이

회전이 되어있더라도 정렬되어있다는 점과, 시간복잡도가 $O(logN)$라는 점에서 이진 탐색이 생각났다.

처음에는 left와 mid값을 비교하는 방식으로 풀어봤지만 다음과 같은 상황이 발생했다.

• left값보다 mid값이 큰 경우: left ~ mid는 정렬되어 있음.
  • 회전이 되어있지 않은 상태(ex. [1,2,3,4,5]): 최솟값이 left값이므로 right = mid
  • $n/2$번 이상 회전되어있는 경우(ex. [3,4,5,1,2]): 최솟값이 mid, right사이에 있으므로 left = mid+1

left값을 비교하는 방법은 포기하고 right값을 비교해보았다.

class Solution:
    def findMin(self, nums: List[int]) -> int:
        if nums[0] < nums[-1]:
            return nums[0]
        left, right = 0, len(nums)-1
        while left < right:
            mid = (left + right) // 2
            if nums[mid] < nums[right]:
                right = mid
            else:
                left = mid + 1
        return nums[left]

• 리스트의 첫번째 숫자가 마지막 숫자보다 작은 경우 회전이 되지 않았다는 것이므로 가장 첫번째 요소를 반환한다.
• left, right를 설정하고 두 값의 중간인 mid를 계산한다.
• 두가지 경우가 있다.
  • mid값보다 right값이 큰 경우: mid ~ right는 정렬되어 있음 = 최솟값이 mid+1과 right사이에 존재하지 않음.
  • mid값이 right값보다 큰 경우: mid ~ right는 정렬되어 있지 않음 = 최솟값이 mid와 right사이에 존재함.
• left와 right가 같아질 때 까지 반복한다.