[Algorithm][LeetCode][Medium][Python] 34. Find First and Last Position of Element in Sorted Array

문제는 여기에서 볼 수 있다.

 

 

읽어보면 굉장히 간단한 문제임을 알 수 있지만,

 

생각보다 빠르게 실행되는 코드를 작성하기 어렵다.

 

 

문제에서는 O(log n)으로 구현해보길 권장하고 있다.

 

---

 

내 풀이

O(log n) 보자마자, 'Two-Pointer 문제인가?' 생각이 들었다.

 

그래서 아래와 같이 구현해봤다.

 

    def searchRange(self, nums: List[int], target: int) -> List[int]:
        result = [-1, -1]
        if not nums:
            return result
        if len(nums) == 1:
            if target == nums[0]:
                return [0, 0]
            else:
                return result
        
        left , right = 0, len(nums) - 1
        while left <= right:
            if nums[left] == target:
                result[0] = left
                while left < len(nums) and nums[left] == target:
                    left += 1
                result[1] = left - 1
                return result
            if nums[right] == target:
                result[1] = right
                while 0 <= right and nums[right] == target:
                    right -= 1
                result[0] = right + 1
                return result
            if nums[left] < target < nums[right]:
                tmp_left, tmp_right = left, right
                while left < len(nums) and nums[left] == nums[tmp_left]:
                    left += 1
                while 0 <= right and nums[right] == nums[tmp_right]:
                    right -= 1
            else:
                return result
        return result

 

입력 리스트에 반복되는 원소들이 좀 많다보니

 

while 문이 잔뜩 들어가버렸다..

 

 

빠르게 실행될 줄 알았는데, 생각보다 결과는 안 좋았다.

 

 

이것저것 코드를 수정해봐도 도통 나아질 기미가 안 보여서 결국 discuss를 뒤져봤다.

 

 

Discuss 풀이

사실 이 문제도 예전에 풀어봤던 문제다.

 

 

그래서 그 때 Discuss를 뒤져서 찾아낸 코드가 있었는데,

 

당시에는 64ms로 굉장히 빠르게 실행되어 상위권 성능을 차지하던 코드였는데

 

지금은 더 빠른 60ms이 나와도 성능 순위가 그 때보다 안좋다.

 

 

아마 파이썬 고수들이 어마무시한 코드를 제출한 모양이다.

 

코드는 아래와 같다.

 

    def binarySearch(self, nums, target, left):
        low, high = 0, len(nums)
        
        while low < high:
            mid = (low + high) // 2
            
            if target < nums[mid] or (left and target == nums[mid]):
                high = mid
            else:
                low = mid+1
            
        return low
    
    def searchRange(self, nums, target):
        left_idx = self.binarySearch(nums, target, True)
        
        if left_idx == len(nums) or nums[left_idx] != target:
            return [-1, -1]
        
        return [left_idx, self.binarySearch(nums, target, False)-1]

 

사용된 알고리즘은 Binary Search 였다.

 

 

굉장히 똑똑한 풀이인데, 사실 binary search는 상상도 못했다.

 

너무 two pointer 알고리즘에만 매달린 것 같다.

 

 

Binary Search 알고리즘의 동작 방식은 알고 있을 것이라 가정하고,

 

이 풀이는 left라는 flag 변수를 두어 변형된 binary search를 수행한다.

 

 

그 left가 가진 boolean 값에 따라 어떤 값을 return 할 것인지 달라지는데,

 

left가 True면 target과 같은 원소를 가진 가장 왼쪽의 인덱스,

 

left가 False면 target과 같은 원소를 가진 가장 오른쪽의 인덱스를 찾는다.

 

 

성능은 아래와 같다.

 

 

 

끝!