[Leetcode 아주 상세한 문제풀이] 33. Search in Rotated Sorted Array - 코드 line 별 설명

Leetcode 문제

이번에 풀어볼 문제는 리트코드 33번 문제 Search in rotated sorted array 다.

우선 문제를 살펴보자.

 

리트코드 33번 문제 Search in rotated sorted array (링크)

Search in Rotated Sorted Array - LeetCode

Search in Rotated Sorted Array - LeetCode

 

 

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Example 3:
Input: nums = [1], target = 0
Output: -1
 
Constraints:
1 <= nums.length <= 5000
-104 <= nums[i] <= 104
All values of nums are unique.
nums is an ascending array that is possibly rotated.
-104 <= target <= 104

 

 

문제 설명

문제를 간략히 살펴보자.

길이가 n인 배열이 주어지고 target 값이 함께 주어진다. 이 배열안의 값들은 모두 다르며 오름차순으로 정렬되어 있다. 하지만 이 오름차순 정렬은 배열의 회전으로 인해 흐트러진 상태로 주어진다. 여기서 회전은 배열 안 값들을 1 회전 당 오른쪽으로 한 칸씩 옮기는 것을 의미한다. 예를 들어 [3, 4, 1, 2]와 같은 배열은 [1, 2, 3, 4] 배열을 2회전 한 것이다.

이때 주어진 target 값과 같은 값이 주어진 배열 안에서 몇번째 인덱스에 위치하는지 그 인덱스 값을 리턴하는 문제다.단, 문제에서 주어진 중요한 제한 조건 중 하나는 time complexity가 O (log n)이어야 한다는 점이다. 이제 문제를 풀어보자.

 

 

문제 접근법

일전에 풀어봤던 153. Find minimum in rorated sorted array와 거의 같은 문제라고 보면 된다.

이전 문제에서는 주어진 배열 안에서 최소값을 찾는 문제였다면,

이번에는 target값이 함께 주어져 그 target 값이 위치한 곳의 인덱스를 찾는 문제다.

이전 문제와 마찬가지로 이번 문제 역시 O (log n)의 time complexity를 갖도록 풀어야 한다.

Time complexity가 O (log n)이라면 binary search로 문제를 풀라는 것을 의미한다.

간단한 예시를 들어 설명해보면 다음과 같다.

우선 [3, 4, 5, 1, 2]와 같은 배열이 주어지고 target=4라고 생각해보자.

153번 문제에서 풀었던 것 처럼 two pointers를 사용해 binary search를 한다.

우선 left pointer는 가장 왼쪽에, right pointer는 가장 오른쪽에 배치시킨다.

그리고 mid pointer는 그 둘 중간으로 정한다.

 

만약 left 포인터에 해당하는 숫자가 mid 포인터에 해당하는 숫자보다 작다면

mid 포인터 왼쪽을 탐색하고 그 반대라면 mid 포인터 오른쪽을 탐색하면 된다.

이때 한 가지 조건이 더 추가되는데, 바로 그 좁혀진 탐색 범위에 target 넘버가 속하는가 있다.

예를 들어 mid pointer 왼쪽 구간을 탐색한다고 할 때

그 구간에 target 넘버가 있다면 우리는 right 포인터를 mid 포인터 왼쪽으로 옮긴다.

target 넘버가 그 구간 안에 있기 때문에 우리는 탐색 범위를 좁혀야 하기 때문이다.

반대로 그 구간 안에 target 넘버가 없다면 mid 포인터 오른쪽에 target 넘버가 있다는 뜻이기 때문에

우리는 left 포인터를 mid 포인터 하나 오른쪽에 옮긴 후 재탐색을 해야 한다.

 

 

문제 풀이

코드로 한 번 살펴보자.

우선 배열와 target 넘버를 입력받을 함수를 정의해 준다 (line 1)

그리고 left는 배열의 가장 왼쪽에 (index=0), right 포인터는 배열의 가장 오른쪽 (index = len(nums)-1)에 위치시킨다 (line 2)

그리고 left 포인터가 right 포인터보다 왼쪽에 있는 동안 while loop를 돌리는데 (line 4)

우선 mid 포인터 위치를 left 포인터와 right 포인터 중간으로 잡아준다 (line 5)

가장 먼저 해야 할 일은 우연하게 mid 포인터가 위치한 곳에 target 넘버가 있을 수도 있기 때문에

mid 포인터에 위치한 값이 target 넘버가 같은지 판단하여 만약 맞다면 그 인덱스를 리턴해준다 (line 7-8)

앞서 설명한대로 binary search를 이용해 탐색 범위를 좁혀나가는데,

만약 left 포인터에 위치한 값이 mid 포인터에 위치한 값보다 작을 경우 (line 10)

mid 포인터 왼쪽을 탐색하여 그 구간 안에 target 넘버가 속하는지 확인한다 (line 11)

만약 target 넘버가 그 구간안에 속한다면 탐색 범위를 좁히기 위해 mid 포인터를 mid 포인터 하나 왼쪽으로 옮긴다.

반대로 그 구간안에 target 넘버가 속하지 않는다면 mid 포인터 오른쪽을 탐색해야 하기 때문에

left 포인터를 mid 포인터 하나 오른쪽으로 옮긴다 (line 13-14)

처음 binary search 조건을 left 포인터에 위치한 값이 mid 포인터에 위치한 값과 비교를 했으므로,

만약 mid 포인터에 위치한 값이 left 포인터에 위치한 값보다 작다면 

mid 포인터 오른쪽 구간을 탐색하면 된다. (line 15-19)

참고로 153번 문제와 달리 배열이 오름차순이라는 사실은 굳이 이용하지 않는다.

while를 다 돌렸는데도 불구하고 만족하는 조건이 없다면 target 넘버가 배열 안에 존재하지 않는 것이므로

마지막에 -1을 리턴해주면 된다 (line 21)

 

 

문제 풀이 코드

def search(nums, target):
    left, right = 0, len(nums) - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if nums[mid] == target:
            return mid
        
        if nums[left] <= nums[mid]:
            if nums[left] <= target <= nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:
            if nums[mid] <= target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
                
    return -1
 
# Test cases
nums1 = [4, 5, 6, 7, 0, 1, 2]
target1 = 0
print(search(nums1, target1))  # Output: 4
 
target2 = 3
print(search(nums1, target2))  # Output: -1
 
nums3 = [1]
target3 = 0
print(search(nums3, target3))  # Output: -1