오름차순으로 정렬된 배열을 회전시킨 배열이 input이다.
해당 배열에서 최소값을 찾으면 되는 문제.
다만, O(logn)으로 풀어야 하기 때문에, 완전탐색이 아닌 이진탐색을 사용해야 한다.
처음 이 문제 보고 그냥 정렬하고 최소값 적용하면 풀리지 않을까?
근데 시간 초과 나겠지 하고 그냥 제출해봤는데
문제 핵심 아이디어
사실 이진탐색은 정렬된 배열에서만 적용된다.
하지만 문제에서 정렬된 배열이지만 회전시켰다고 해서, 이진탐색이 가능한가? 생각했었다.
근데 조금만 더 생각해보면, 이미 오름차순으로 정렬된 배열을 회전시켰기 때문에 2 개의 정렬된 서브배열이 있다는 것을 알 수 있다! (핵심)
[3, 4, 5, 1, 2]가 있다면
[3, 4, 5], [1, 2]처럼 서브배열이 나뉜다고 생각하면 된다.
그 기준으로는 nums[mid] >= nums[left]가 될 수 있다.
조건 만족한다면, nums[mid]의 값은 left 서브배열에 있다는 것이고 right 서브배열을 탐색하도록 해야 한다.
조건 만족하지 않는다면, nums[mid]는 right 서브배열에 있고 그 중에서도 가장 작은 값을 찾아야 하기 때문에 mid - 1을 right 값으로 할당한다.
class Solution:
def findMin(self, nums: List[int]) -> int:
left, right = 0, len(nums) - 1
res = nums[0]
while left <= right:
# 정렬되어 있을 경우
if nums[left] < nums[right]:
res = min(res, nums[left])
break
mid = (left + right) // 2
# mid 값이 바뀔 때마다 최소값 갱신
res = min(res, nums[mid])
if nums[mid] >= nums[left]:
# right search
left = mid + 1
else:
# left search
right = mid - 1
return res