LeetCode 81(Search in Rotated Sorted Array II, Python)

1. 문제 링크

• https://leetcode.com/problems/search-in-rotated-sorted-array-ii/

Search in Rotated Sorted Array II - LeetCode

2. 문제 설명

• 오름차순으로 정렬된 리스트가 한번 회전 되어 주어졌을 때 특정 값이 포함되어 있는 지 조사하여 True or False를 반환하는 문제
• 예시) 리스트 [0,0,1,2,2,5,6]를 한번 회전하여 nums = [2,5,6,0,0,1,2], target = 0이 주어졌을 때 0이 포함되므로 True 반환

3. 처음 풀이

• return target in nums 하면 런타임 자체는 좋게 나오지만 시간 복잡도가 O(n)으로 의도한 풀이가 아닐 것.
• 중간에 한 번 회전된 것, 중복값이 있음을 고려하여 이진 검색을 하면 된다.
• 중간 지점을 정하면 왼쪽 또는 오른쪽 중 한 쪽은 오름차순 정렬이 되어 있다.
• 내가 찾는 값이 정렬된 곳에 있을 것으로 기대되면 거기에서 일반적인 이진 검색을 시행하면 되고, 정렬되지 않은 곳에 있을 것으로 기대되면 그 곳을 또 반으로 쪼개어 반복한다.
• 그리고 중복 값이 있으면 포인터를 옮기도록 하자.

class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        left, right = 0 , len(nums) - 1

        while left <= right:
            if nums[left] == target or nums[right] == target:
                return True

            while left < len(nums) - 1 and nums[left] == nums[left + 1]: #이 부분이 느림. 필요할 때만 이 작업을 해야함.
                left += 1
            while right > 0 and nums[right] == nums[right - 1]: #이 부분이 느림. 필요할 때만 이 작업을 해야함.
                right -= 1
            
            mid = (left + right) // 2

            if nums[mid] == target:
                return True
            elif nums[mid] < nums[right]:
                if nums[mid] < target < nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1
            else:
                if nums[left] < target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
        
        return False

4. 다른 풀이

• 중복 값을 생략하기 위해 포인터를 한 칸씩 옮겨주는 건 어느 쪽이 정렬되었는 지 모를 때만 하면 된다.

class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        begin = 0
        end = len(nums) - 1 
        while begin <= end:
            mid = (begin + end)//2
            if nums[mid] == target:
                return True
            if nums[mid] == nums[end]: # 중앙과 오른쪽 끝이 같다면 어느 쪽이 정렬되어 있는 지 모름
                end -= 1  # 오른쪽 끝을 한 칸 앞으로, 최악의 경우 O(n)
            elif nums[mid] > nums[end]: # 중앙이 오른쪽보다 크다면 왼쪽이 오름차순 정렬됨. 
                if  nums[begin] <= target and target < nums[mid]: # 왼쪽 끝 <= target < 중앙 이면왼쪽에서 찾기
                    end = mid - 1
                else: # 그렇지 않다면 오른쪽에서 찾기
                    begin = mid + 1
            else: # 오른쪽이 오름차순 정렬됨. 
                if  nums[mid] < target and target <= nums[end]: # 중앙 < target <= 오른쪽 끝이면 오른쪽에서 찾기
                    begin = mid + 1
                else: # 그렇지 않다면 왼쪽에서 찾기
                    end = mid - 1
        return False

5. 배운 점

• 중복 값 처리할 때 너무 아무 생각 없이 했는데 최적화에서 꽤 차이가 났다.