Leetcode 33. Search in Rotated Sorted Array - Python

Leetcode 33 문제 보기

 

문제 이해하기

오름차순으로 정렬된 어떤 정수의 리스트 nums가 특정 값을 기준으로 회전되었다.

예를 들어 [1,2,3,4]가 3을 기준으로 회전되면 [3,4,1,2]가 된다.

 

어떤 정수 target이 주어질 때, 해당 target이 nums안에 존재하는지 판단하고

만약 존재한다면 그 숫자의 nums내 index값을 반환하고, 존재하지 않는다면 -1을 반환하라.

단, 알고리즘은 O(logn)의 시간복잡도를 가져야 한다.

 

아이디어 구상

단순히 target이 nums에 있는지 알기위해서는 리스트를 순차적으로 탐색하면서 있는지 없는지 판단하면 될 것이다.

그러나 이는 O(n)의 시간복잡도를 가진다.

 

때문에 O(logn)의 시간복잡도를 가지기 위해서는 결국 Binary Search를 해야한다.

 

그런데 여기서 문제가 생긴다.

이분탐색을 하기 위해서는 원소가 정렬되어 있어야 한다.

그러나 주어진 리스트 nums는 특정 값을 pivot으로 회전되어 있다.

즉, 정렬되어 있지 않다.

 

그러나 엄밀히 말하자면 nums는 '정렬된 두 리스트가 합쳐진' 리스트다.

때문에 2번의 Binary Search를 통해 정답을 구할 수 있겠다.

By Mesotes

 

따라서 Left portion 일 때, 이분 탐색을 하는 코드와

Right portion 일 때, 이분 탐색을 하는 코드를 작성하여 target의 존재여부를 판별하자.

 

풀이

Binary Search를 위해 양 끝의 포인터를 선언하자.

left, right = 0, len(nums) - 1

 

이제 left가 right을 초과하기 전까지 while문을 통해 탐색을 진행한다.

이때 mid, 즉 중간값을 구하는 수식에 주의하자.

비록 파이썬에서는 크게 고려하지 않아도 되지만, overflow를 방지하기 위해 (left + right) // 2가 아닌 left + ((right - left) // 2)로 표시하는 습관을 기르자.

while left <= right:
    mid = left + ((right - left) // 2)
    # Search whether there's target or not

 

탐색을 진행하며 만약 target을 찾았다면 해당 숫자의 index를 반환하자. (종료 조건)

if target == nums[mid]:
    return mid

 

좌우 portion에 대해 Binary Search를 진행한다.

만약 nums[left]가 nums[mid]보다 작거나 같다면 monotonic하게 증가하고 있다는 의미이며, 때문에 같은 portion내에 존재한다는 의미가 된다. 그렇지 않을 경우, 현재 mid는 right portion에 존재하게 된다.

# left portion
if nums[left] <= nums[mid]:
    if target > nums[mid] or target < nums[left]:
        left = mid + 1
    else:
        right = mid - 1
            
# right portion
else:
    if target < nums[mid] or target > nums[right]:
        right = mid - 1
    else:
        left = mid + 1

 

전체 코드는 다음과 같다.

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        
        while left <= right:
            mid = left + ((right - left) // 2)
            # find target
            if target == nums[mid]:
                return mid
            
            # left portion
            if nums[left] <= nums[mid]:
                if target > nums[mid] or target < nums[left]:
                    left = mid + 1
                else:
                    right = mid - 1
            
            # right portion
            else:
                if target < nums[mid] or target > nums[right]:
                    right = mid - 1
                else:
                    left = mid + 1
            
        return -1

---

 

Leetcode 33. Search in Rotated Sorted Array

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

​

 

 

 

-문제해결흐름을 간단히 정리한 주관적 포스팅-

 

-부족한 설명이 있다면 부디 조언 부탁드립니다-

 

 

 

 

이 포스팅은 쿠팡 파트너스 활동의 일환으로,

이에 따른 일정액의 수수료를 제공받습니다