[리트코드] Search in Rotated Sorted Array(python)

리트코드, Search in Rotated Sorted Array_회전 정렬 배열 탐색

Search in Rotated Sorted Array - LeetCode

TL;DR

• 이진 탐색(Binary search)

문제 요약

1. 서로 다른 값을 가진 오름차순으로 정렬된 리스트 nums가 주어진다.
2. 이 리스트는 특정 pivot 인덱스에 의해 회전된 형태로 존재할 수 있다.
    2-1. 예를 들어 [0, 1, 2, 4, 5, 6, 7] 리스트에 대해 pivot 인덱스가 3이라면 회전된 리스트는 [4, 5, 6, 7, 0, 1, 2]가 된다.
3. 이러한 특징을 가진 리스트 nums에서 target이 존재한다면 해당 인덱스를 반환하고, 존재하지 않는다면 -1을 반환한다.
4. 시간 복잡도는 O(logn)을 만족해야 한다.

 

- 정렬된 리스트가 주어지지만 이 리스트는 pivot 인덱스만큼 시작 지점이 이동한 형태가 될 수 있다. 이 pivot 인덱스는 주어지지 않는다.

- 정렬된 배열이고 시간 복잡도가 O(logn)으로 제한되기 때문에 Binary search를 통해 문제를 해결할 수 있다.

- 회전된 pivot 인덱스를 찾으면 해당 인덱스부터 정렬된 리스트임을 알고 있기 때문에 Binary search를 진행할 수 있다. 문제 풀이의 핵심은 정렬된 리스트의 시작 지점을 찾고, Binary search를 수행할 때, pivot 인덱스를 활용하는 것이다.

입출력 형태

입출력 예시

풀이

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        # 1. 시작 지점이 되는 지점 찾기
        nums_start = nums.index(min(nums))
        
        # 2. binary search를 통해 원하는 값 찾기
        low, high = 0, len(nums) - 1
        while low <= high:
            mid = (low + high) // 2
            actual_mid = (nums_start + mid) % len(nums)
            
            if nums[actual_mid] == target:
                return actual_mid
            elif nums[actual_mid] < target:
                low = mid + 1
            else:
                high = mid - 1
            
        return -1

 

두 가지 부분으로 나누어서 살펴볼 수 있다.

첫 번째는 pivot 인덱스를 찾는 것이다.

- 오름차순으로 정렬된 리스트라고 문제에서 말했기 때문에 가장 작은 값의 인덱스를 찾아 해당 인덱스를 pivot index로 두었다.

두 번째는 target을 찾는 것이다.

- 첫 번째 작업을 통해 pivot 인덱스를 찾았기 때문에 Binary search를 수행할 수 있다.

- 우선, 일반적으로 Binary search를 하는 것처럼 투 포인터를 통해 중간 지점인 mid를 찾는다.

   - 이 mid는 리스트가 시작하는 인덱스가 0일 때의 중간 지점이다. 즉, 다르게 표현하면 0 + mid가 되는 것이다.

   - 하지만, 리스트는 pivot 인덱스부터 시작하므로 mid로 Binary search를 진행할 경우 원하는 답을 얻지 못한다. 우리가 필요한 것은 pivot 인덱스부터의 mid값이다.

- 이를 위해 mid에 pivot 인덱스를 더해준다. 단, 단순 덧셈만 할 경우 리스트의 크기를 넘어가기 때문에 IndexError가 발생할 수 있다. 따라서 배열의 크기로 나눈 나머지로 설정해준다. 이렇게 되면 정렬된 리스트에서의 mid 값을 알게 된다.

   - 예시 1에서 pivot 인덱스는 4이고, mid는 3이다. pivot 인덱스와 mid를 더한 값은 7인데, 이는 리스트의 길이로 나누면 0이 된다.

   - 주어진 리스트에서 0번 인덱스의 값은 4이다. 주어진 리스트를 원래 정렬된 리스트로 바꾸면 [0, 1, 2, 4, 5, 6, 7]이다. 0번 인덱스의 값인 4가 결국 본래 정렬된 리스트의 중간과 같은 것이다.

- 이제 Binary search에 필요한 mid 값을 알았기 때문에 나머지는 Binary search를 수행하는 코드를 작성하면 된다. 만약 actual_mid의 값이 target의 값과 같다면 해당 값을 반환하고, 그렇지 않은 경우에 대해서는 각각 low와 high에 적절한 값을 할당한다. 반복문이 수행되는 동안 target을 찾지 못했다면 해당 경우는 target이 존재하지 않는 경우이므로 -1을 반환한다.