Week 2-2. [Binary Search] 33. Search in Rotated Sorted Array (Python3)

문제 해결 과정

✍️ 나만의 방식으로 문제 정리하기 (=체계화)

https://leetcode.com/problems/search-in-rotated-sorted-array/?envType=study-plan-v2&envId=top-interview-150 

Search in Rotated Sorted Array - LeetCode

오름차순 정렬된 배열이 rotate 된 상태로 주어진다. O(log n)의 시간안에 특정 값을 탐색하여 인덱스를 반환하라.

• nums의 길이는 [1, 5000]이다.
• 배열 안에 target이 존재하지 않으면 -1을 반환한다.
• 시간 복잡도 O(log n)안에 구현해야 한다.

🔎 어떤 식으로 접근했는가?

mid를 중심으로 반을 나눴을 때, 반드시 한 쪽은 정렬된 상태일 것이다.

 

정렬된 상태는 어떻게 알 수 있을까?

nums[lp] <= nums[mid]라면 왼쪽 부분이 정렬된 상태인 것이고, 그게 아니라면 오른쪽 부분이 정렬된 상태인 것이다.

 

만약 왼쪽이 정렬되어 있다면,

nums[lp] <= target < nums[mid]로 target이 왼쪽에 있는지 알아보고,

target이 존재하지 않는다면 target은 오른쪽에 있는 것이다.

 

혹은 오른쪽이 정렬되어 있다면,

nums[mid] < target <= nums[rp]로 target이 오른쪽에 있는지 알아보고,

target이 존재하지 않는다면 target은 왼쪽에 있는 것이다.

 

이렇게 반복하다보면 target을 찾거나 혹은 -1을 반환하게 된다.

 

🙈 알고리즘 선택: 입력의 크기를 바탕으로

O(log n)의 시간복잡도에 해결하라는 조건이 주어졌으므로 binary search를 이용한다.

 

📝 의사 코드

lp, rp = 0, len(nums)-1

lp가 rp보다 작거나 같은 동안:
	mid = (lp+rp)//2
    if nums[mid]가 target과 같다면: return mid
    elif 왼쪽 부분이 정렬되어 있다면:
    	if target이 왼쪽에 있다면: rp = mid-1
        else: lp = mid+1
    else 오른쪽 부분이 정렬되어 있다면:
    	if target이 오른쪽에 있다면: lp = mid+1
        else: rp = mid-1
    return -1

 

🎯 구현 코드

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

        while lp <= rp:
            mid = (lp+rp) // 2
            if nums[mid] == target: return mid
            elif nums[lp] <= nums[mid]: # 왼쪽 정렬O && 오른쪽 정렬X
                if nums[lp] <= target < nums[mid]: # target이 왼쪽에 있는 경우
                    rp = mid-1
                else: # target이 오른쪽에 있는 경우
                    lp = mid+1
            else: # 왼쪽 정렬X && 오른쪽 정렬O
                if nums[mid] < target <= nums[rp]: # target이 오른쪽에 있는 경우
                    lp = mid+1
                else: # target이 왼쪽에 있는 경우
                    rp = mid-1
        return -1

 

내 코드를 탐구해보기

⏱ 성능 측정 (시간복잡도/공간복잡도)

binary search를 이용하여 절반씩 대상을 줄여나갔으므로 O(log n)이다.

 

✍️ 성능 회고

1초 제한에서 O(log n)의 최대 입력은 10^7~10^8이다. 문제에서는 최대 입력이 5000이므로 성능이 좋은 편이다.

 

다른 사람의 코드를 탐구해보기

🎯 구현 코드

출제자의 의도는 아니겠지만 파이썬 내장 함수를 이용해 아래처럼 간단하게 풀 수도 있다.

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        try:
            return nums.index(target)
        except:
            return -1

 

⏱ 성능 측정 (시간복잡도/공간복잡도)

list.index()의 시간 복잡도는 O(n)으로 이진 탐색보다 느리다.

 

느낀 점

binary search의 개념은 알고 있었지만 rotate된 배열에 적용하기는 생각보다 까다로웠다.

손으로 예시를 직접 만들어가며 로직을 짜는 것이 도움이 되었다.