Search for a Range | LeetCode 802 | Python3 🐍

 

📄 목차

 

 

🤔 문제 : Longest Palindromic Substring | LeetCode 802

문제: https://leetcode.com/explore/interview/card/top-interview-questions-medium/110/sorting-and-searching/802/

정렬된 배열에서 타겟이값이 나오는 구간을 찾는 문제입니다.

time complexity 를 O(logN)으로 하라는 단서가 있습니다. 

 

💡 풀이

1. Binary Search

시작점, 끝점을 찾는 binary search를 두번 수행하는 방식으로 코드를 작성했습니다.

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        last_idx = len(nums)-1
        if not nums: return [-1, -1]
        # binary search
        def bs(stIdx, edIdx, searchStart = True):
            if stIdx > edIdx: return -1
            md = int((stIdx+edIdx)/2)
            if nums[md] < target: return bs(md+1, edIdx, searchStart)
            if nums[md] > target: return bs(stIdx, md-1, searchStart)
            if nums[md] is target:  [1]
                if searchStart:	[2]
                    if md == 0 or nums[md-1] < target: return md
                    else: return bs(stIdx, md-1, searchStart)
                else:		[3]
                    if md == last_idx or nums[md+1] > target: return md
                    else: return bs(md+1, edIdx, searchStart)
        return [bs(0, last_idx), bs(0, last_idx, False)]

[1] 리스트의 중간 값이 target값과 일치할 때 시작점을 찾는 케이스와 끝점을 찾는 케이스를 분기합니다. 

[2] 시작점을 찾을 때는, 바로 전 값이 타겟값보다 작은지 확인합니다.

작지 않다면, 지금보다 왼쪽 범위에서 다시 시작점을 찾습니다. 

[3] 시작점을 찾을 때는, 바로 다음 값이 타겟값보다 큰지 확인합니다.

크지 않다면, 지금보다 오른쪽 범위에서 다시 시작점을 찾습니다. 

 

Time Complexity
O(2*logN)
퀵소트를 두번 하는 방식입니다.

 

 

2. Binary Search + loop

Binary Search로 타겟 값을 찾고, 왼쪽 오른쪽을 쭉 확인하며 같은 값이 나오는 인덱스까지를 반환하는 방식입니다.

 

[5,5,5,5, ... 5], target : 5 

위와 같이 전체 배열이 다 같은 값인 케이스에 대해서는, 사실상 전체 배열을 확인하게 되므로 Time complexity는 O(N)이 됩니다. 

문제의 조건을 만족하는 풀이는 아니겠죠.

하지만 연산 자체가 간단하여, 수행시간은 훨신 빠르게 나오네요. 

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        last_idx = len(nums)-1
        if not nums: return [-1, -1]
        # binary search
        def bsRange(stIdx, edIdx):
            if stIdx > edIdx: return [-1, -1]
            md = int((stIdx+edIdx)/2)
            if nums[md] < target: return bsRange(md+1, edIdx)
            if nums[md] > target: return bsRange(stIdx, md-1)
            if nums[md] is target:
                st = md
                while 1:
                    if st is -1 or nums[st] != target: break
                    st -= 1
                ed = md
                while 1:
                    if ed == last_idx+1 or nums[ed] != target: break
                    ed += 1
                return [st+1, ed-1]

        return bsRange(0, last_idx)

 

Time Complexity
O(N)
최악의 경우 전체 배열 순회

 

3. Python  cheat - bisect

파이썬에서 기본으로 제공하는 binary search라이브러리를 활용한 풀이입니다.

 

• bisect.bisect_left :  정렬된 순서를 유지하도록 a에 x를 삽입할 위치를 찾습니다. x가 a에 이미 있으면, 삽입 위치는 기존 항목 앞(왼쪽)이 됩니다.
• bisect.bisect_right :  정렬된 순서를 유지하도록 a에 x를 삽입할 위치를 찾습니다. x가 a에 이미 있으면, 삽입 위치는 기존 항목 뒤(오른쪽)이 됩니다.

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        if not nums: return [-1, -1]
        left,right = bisect.bisect_left(nums, target), bisect.bisect_right(nums, target)
        return [left, right - 1] if left < right else [-1, -1]

 

에러케이스

binary search를 오랜만에 짜다보니.. 인덱스 잡는 부분이나 엣지케이스를 고려 하지 못한 부분들이 있었습니다.

아래는 제가 놓쳤던 에러케이스들입니다.

 

print(Solution().searchRange([2, 2], 3))
print(Solution().searchRange([2, 2], 2))
print(Solution().searchRange([], 0))

 

 

is vs ==

is가 가독성이 좋아 무지성(?)으로 쓰고 있었는데, 이 때문에 오답이 나기도 했습니다.

• is는 변수가 같은 Object(객체)를 가리키면 True
• ==는 변수가 같은 Value(값)을 가지면 True

파이썬은 -5~256 범위의 숫자를 미리 할당해놓습니다.

그래서 이 범위의 숫자를 is 연산으로 비교하면 같은 Object를 가리키므로 true이지만,

이 범위를 넘는 숫자에 대해서는 숫자를 새로할당하여 주소가 달라지므로, 같은 값이라도 is비교 시 false가 됩니다. 

 

아래는 문제가 되었던 코드와 에러케이스입니다.

 

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        last_idx = len(nums)-1
        if not nums: return [-1, -1]
        # binary search
        def bs(stIdx, edIdx, searchStart = True):
            if stIdx > edIdx: return -1
            md = int((stIdx+edIdx)/2)
            if nums[md] < target: return bs(md+1, edIdx, searchStart)
            if nums[md] > target: return bs(stIdx, md-1, searchStart)
            if nums[md] is target:
                if searchStart:
                    if md is 0 or nums[md-1] < target: return md
                    else: return bs(stIdx, md-1, searchStart)
                else:
                    if md is last_idx or nums[md+1] > target: return md # [1]
                    else: return bs(md+1, edIdx, searchStart)
        return [bs(0, last_idx), bs(0, last_idx, False)]
        
        # print(Solution().searchRange([5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5], 5))

[1] 문제가된 부분입니다. num에 길이가 매우 긴 배열이 들어올 경우 md, last_idx 값이 256 이상이 됩니다. 이러면, is비교에서 예상치못하게 false가 됩니다.