•
문제 설명 : 주어진 배열에서 가장 작은 값을 찾아 반환한다. 단, 주어진 배열은 정렬된 배열에서 회전된 배열일 수 있다.
•
풀이 방법
◦
각 요소의 간격이 동일한 배열에 대해서는 처리했지만, 불규칙한 배열은 처리하지 못하였다.
◦
나는 이진 탐색을 사용하고, 범위의 양 끝 값을 비교하는 방법을 사용했었다.
▪
하지만, 불규칙한 배열의 경우에는 값의 차이로 구하는 것은 큰 의미가 없었다.
•
시간복잡도 :
•
실패 코드(간격이 다른 배열의 경우 실패)
class Solution:
def findMin(self, nums: List[int]) -> int:
left, right = 0, len(nums) - 1
while right - left > 1:
mid = (right + left + 1) // 2
padding = min(abs(left - mid), abs(right - mid))
if abs(nums[mid] - nums[mid - padding]) < abs(nums[mid] - nums[mid + padding]):
left = mid
else:
right = mid
return min(nums[left], nums[right])
Python
복사
•
성공 코드
Solution의 코드의 경우, 내가 작성한 코드보다 더 간단하게 생각하였다.
복잡하게 생각하면 더 어려워지는 것 같다.
◦
중간 값 > 범위 오른쪽 끝 값 → 범위 오른쪽에 최소 값이 있다.
▪
정렬된 값이라면, 보통 오른쪽으로 갈수록 커지기 때문에 오른쪽이 더 작은 경우에는 최소 값이 있다고 생각할 수 있다.
# 해당 코드는 오른쪽과 비교하며 진행하는 코드이다.
class Solution:
def findMin(self, nums: List[int]) -> int:
left = 0
right = len(nums) - 1
while left < right:
mid = (left + right) // 2
if nums[mid] > nums[right]:
left = mid + 1
else:
right = mid
return nums[right]
Python
복사