문제 개요
-
오름차순으로 정렬된 배열을 회전시킨 배열이 input이다.
-
해당 배열에서 최소값을 찾으면 되는 문제.
-
다만, O(logn)으로 풀어야 하기 때문에, 완전탐색이 아닌 이진탐색을 사용해야 한다.
풀이 구상
-
처음 이 문제 보고 그냥 정렬하고 최소값 적용하면 풀리지 않을까?
-
근데 시간 초과 나겠지 하고 그냥 제출해봤는데
- 풀리긴 했다.
- 문제 의도는 이게 아니므로 다시 이진탐색으로 접근.
문제 핵심 아이디어
-
사실 이진탐색은 정렬된 배열에서만 적용된다.
-
하지만 문제에서 정렬된 배열이지만 회전시켰다고 해서, 이진탐색이 가능한가? 생각했었다.
-
근데 조금만 더 생각해보면, 이미 오름차순으로 정렬된 배열을 회전시켰기 때문에 2 개의 정렬된 서브배열이 있다는 것을 알 수 있다! (핵심)
-
[3, 4, 5, 1, 2]가 있다면
[3, 4, 5], [1, 2]처럼 서브배열이 나뉜다고 생각하면 된다.- 결국 최소값은 right 서브배열에 있다.
- 이진탐색의 mid 값이 어떤 서브배열에 있는지 판단하는 것이 중요한 기준이 된다!
-
그 기준으로는 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- 시간복잡도: 이진탐색을 적용했기 때문에 O(logn)
Software Developer