leetcode medium : Search in Rotated Sorted Array II

Search in Rotated Sorted Array II - LeetCode

Search in Rotated Sorted Array II - LeetCode

 

와 ㅋㅋㅋㅋ

이건 느낌이 왔다. 무조건 O(log N)으로 풀어야된다. 무조건 ㅋㅋㅋ

 

binary search는 무조건 탐색 범위 내의 숫자들이 다 정렬되어있어야되는데,

그러면 어디가 rotated된 지점인질 찾아야된다. 근데 그럼 rotated point를 찾는 선형 탐색이 O(N)을 먹게되잖아.

배보다 배꼽이 더 커지면 안되지.

 

음 내생각엔 피벗포인트 자체를 이진탐색으로 찾은 다음에

target과 피벗포인트 숫자의 대소를 비교하고

양쪽 list중 하나를 택해 binary search를 수행해야한다.

 

이진탐색을 변형해서 구현해야되기 때문에 bisect같은 라이브러리 함수는 당연히 못쓰고

직접 상황에 맞게 구현할 수 있는 능력이 필요하다. 그리고 문제가 시리즈로 나온걸 보니

FAANG 인터뷰 질문의 냄새가 아주 진하게 난다. 이정도는 30분안에 입을 쉬지 않고 설명하면서

풀고 복잡도 분석까지 할 수 있어야 FAANG에 들어가는구만.

 

class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        
        low = 0
        high = len(nums) - 1
        
        while low < high:
            mid = (low + high) // 2
            
            if nums[low] > nums[mid]:
                high = mid
            elif nums[mid] > nums[high]:
                low = mid + 1
            else:
                break
                
        rotated_point = low
        
        if target == nums[rotated_point]:
            return True
        elif target > nums[rotated_point]:
            low = rotated_point
            high = len(nums)
        else:
            low = 0
            high = rotated_point
            
        while low < high:
            mid = (low + high) // 2
            
            if nums[mid] < target:
                low = mid + 1
            else:
                high = mid
                
        return low != len(nums) and nums[low] == target

 

이런 쓰레기 코드를 또 짜버렸다. 이게 모든 value가 distinct value면 괜찮은 코드인데 [1, 0, 1, 1, 1] 이런식으로 숫자가 들어오면 rotated point 찾는거 자체가 안돼버리네.. log 타임에 푸는게 정녕 불가능한 것인가..

 

 discussion을 보니까 worst case는 어쩔수 없이 O(N)이 되어버리는거같다. 다들 O(log N) 솔루션이라고 올리는데 잘 보면 중복을 제거하는 과정에서 O(N)이 되어버린다 ㅋㅋ ㅠ

 

class Solution:
    def find_rotated_point(self, nums):
        low = 0
        high = len(nums) - 1
        
        while low < high:
            while low < len(nums) - 1 and nums[low] == nums[low + 1]:
                low += 1
            while high > 1 and nums[high] == nums[high - 1]:
                high -= 1
            
            mid = (low + high) // 2
            
            if nums[low] > nums[mid]:
                high = mid
            elif nums[mid] > nums[high]:
                low = mid + 1
            else:
                break
                
        return low
    
    def binary_search(self, nums, low, high, target):
        while low <= high:
            mid = (low + high) // 2
            
            if nums[mid] == target:
                return True
            elif nums[mid] < target:
                low = mid + 1
            else:
                high = mid - 1
        return False
    
    def search(self, nums: List[int], target: int) -> bool:
        rotated_point = self.find_rotated_point(nums)
        
        left = self.binary_search(nums, 0, rotated_point - 1, target)
        right = self.binary_search(nums, rotated_point, len(nums) - 1, target)
        
        return left or right

 

가독성 적당하고 구현 난이도도 적당하고 time & space complexity도 적당한 코드 완성 ㅋㅋㅋ