⭐️ LeetCode 알고리즘 풀이 (with Python)

# Find First and Last Position of Element in Sorted Array

[Quetion]

LeetCode 34. Find First and Last Position of Element in Sorted Array

📌 접근법

[문제 이해]

• 오름차순으로 정렬된 배열에서 target값의 시작점과 끝나는 지점을 반환
• target 값이 없는 경우 [-1, -1] 반환
• O(log N)의 시간복잡도

O(log N)의 시간복잡도이기 때문에 이진탐색의 방법으로 접근해야한다.
처음 지점을 가리키는 l 포인터, 끝 지점을 가리키는 r 포인터를 활용하여 다음과 같이 생각했다.

• l <= r 만큼 반복
• mid = (l+r)//2 일때 nums[mid]가 target보다 크면 r 포인터를 mid - 1로 옮긴다.
• 반대면 l 포인터를 mid + 1로 옮긴다.
• 만약 nums[l]이 target과 같지 않으면 l포인터를 1씩 증가시킨다.
• nums[r]이 target과 같지 않으면 r 포인터를 1씩 증가시킨다.
• nums[l]이 가리키는 값과 nums[r]이 가리키는 값이 target과 일치하면 l, r을 반환

💻 구현

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        l,r = 0, len(nums)-1
        while l <= r:
            mid = (l+r)//2 
            if nums[l] == nums[r] == target:
                return [l, r]
            # 중앙값이 target 보다 크고 작은 경우 l, r 옮김
            if nums[mid] > target:
                r = mid - 1 
            if nums[mid] < target:
                l = mid + 1
            # l과 r 포인터 1칸씩 이동
            else:
                if nums[l] != target:
                    l += 1
                if nums[r] != target:
                    r -= 1
        return [-1, -1]

Runtime: 78ms | Memory: 17.7MB
LeetCode 코드 중 Runtime 87%, Memory 90% 해당하는 결과

📌 로직 핵심

• 중앙값과 target값 비교상황 이외에도 l과 r 포인터를 1칸씩 이동
• l과 r이 가리키는 값이 target 값과 같으면 l, r이 target의 시작과 끝점을 가리키는 것

📝 Find First and Last Position of Element in Sorted Array 회고

• 시간복잡도는 이진검색을 활용하여 O(log N)이고, 공간복잡도는 O(1)을 가진다.

• 처음에는 일반적인 이진검색 알고리즘을 활용하여 중앙값에 따라 l과 r 포인터만 움직였지만 틀렸었다.

• 그래서 중앙값과 target의 비교 이외에도 l과 r이 가리키는 값을 각각 target과 비교함으로써 l, r의 포인터를 한 칸씩 움직이는 것을 추가했다.

• 더 이상 어떻게 성능적으로 개선해 볼 수 있을지는 떠오르지 않아서 코드 수정은 하지 않았다.

• 문제를 해결하고 다른 솔루션을 보니 재귀를 활용한 코드가 간단해서 인상 깊었다. 그리고 현재 코드와 동일한 방법으로 해결한 코드들이 많았던 것을 확인할 수 있었다.