728x90
반응형
https://leetcode.com/problems/search-in-rotated-sorted-array/
얼핏보면 간단한 문제 같지만 O(logn)이라는 조건이 붙어있는만큼, Binary Tree 로 풀어야 하는 문제였습니다
class Solution:
def search(self, nums: List[int], target: int) -> int:
return nums.index(target) if target in nums else -1
저처럼 이렇게 풀면 안되는,,,,
얼마전에 Binary Search Tree를 공부했기 때문에 그래도 코드를 이해하면서 따라갈 수 있었는데요
2022.09.26 - [분류 전체보기] - Binary Tree & Binary Search Tree
Binary Search Tree의 원리를 활용한 풀이를 살펴보겠습니다!
class Solution:
def search(self, A: List[int], target: int) -> int:
n = len(A)
left, right = 0, n - 1
if n == 0: return -1
while left <= right:
mid = left + (right - left) // 2
if A[mid] == target: return mid
if A[mid] >= A[left]:
if A[left] <= target < A[mid]:
right = mid - 1
else:
left = mid + 1
else:
if A[mid] < target <= A[right]:
left = mid + 1
else:
right = mid - 1
우선 Binary search Tree의 주목적이 뭘지 생각해보면 일일이 다 찾는게 아니라 왼쪽 자식 노드는 root 보다 작은 값,
오른쪽은 더 큰 값이 있는 구조상의 특성을 활용해서 더 빨리 값을 찾자는데에 목적이 있습니다.
이 문제에서는 A[mid] >= A[left] 왼쪽으로 rotate했을 때 만약에 값이 중간값 기준 왼쪽에 있으면 left rotation을 \
실행했다는거겠죠. 만약 값이 시작점에서 중간값 사이에 있다면 mid보다 큰 값은 볼 필요가 없어지기 때문에 mid-1을 해주고 그렇지 않다면 반대쪽에 있는 것이기 때문에 mid+1을 해주겠죠
똑같은 논리를 바탕으로 right rotation한 상황을 생각해보고 점차 값을 좁혀 나가면 A[mid] == target이 되는 값을 찾을 수 있게 됩니다
728x90
반응형
'‼ ERROR RECORD' 카테고리의 다른 글
Leetcode 56. Merge Intervals (0) | 2022.09.29 |
---|---|
Leetcode 19. Remove Nth node from end of the list (Linked List, two-pointer) (0) | 2022.09.28 |
Leetcode 200. Number of Islands (Union Find) (0) | 2022.09.27 |
Leetcode. Coin Change (DP, BFS) (0) | 2022.09.25 |
Leetcode 207. Course Schedule 풀이 (Topological Sorting, BFS, DFS) (1) | 2022.09.23 |
댓글