[LeetCode] 33. Search in Rotated Sorted Array (파이썬)

33. Search in Rotated Sorted Array - 파이썬 풀이

• 해당문제 링크

  목차

1. 문제풀이 아이디어
2. 구현코드

문제풀이 아이디어

• 먼저 해당 문제에서 요구하는 것을 알아보자. 풀어서 적어보면 nums라는 오름차순으로 정렬된 배열을 일정 칸만큼 로테이션한 배열에서 target의 인덱스는 어디인가? 이다.
• 그렇다면 배열이란 뭘까? 하나의 데이터형의 여러 데이터들을 연속적인 메모리 공간에 순차적으로 저장하는 자료구조이다. 이 배열에서 위에서 요구하는 것처럼 target이란 데이터가 어느 인덱스에 있는지 알고 싶다면 어떻게 해야할까? 바로 탐색이다.
• 배열에서 탐색하는 알고리즘은 완전탐색, 이진탐색, 슬라이딩 윈도우, 투 포인터 등이 있다. 하지만 해당 문제에서 요구하는 시간 복잡도는 O(logN)이다. 이를 만족하는 탐색 알고리즘은 이진탐색 밖에 없다.
• 이진탐색을 하려고 하니 nums는 정렬된 배열이 아니다. 그 이유는 정렬된 배열을 랜덤 인덱스 수 만큼 로테이션 시켰기 때문이다.
• 그렇기 때문에 그냥 이진탐색을 수행할 수 없다. 그 이유는 이진탐색은 pivot의 값과 비교해서 작거나 큰 경우에 따라 탐색 범위를 줄여나가는 알고리즘이기 때문이다.
• 그럼 이를 해결하기 위해선 nums를 정렬을 시켜야 하는가? 그것도 불가능하다. 그 이유는 요구하는 시간 복잡도는 O(logN)인데 정렬알고리즘 중에 O(logN)을 만족하는 알고리즘이 없다. 그렇다면 무조건 이진탐색을 이용해야한다.
• 이진탐색으로 이를 해결할 수 있을 것 같은 이유는 배열이 정렬되었었다가 특정 규칙으로 변해있기 때문이다. 그말은 경우들을 생각해서 특정 조건을 걸게 되면 정렬된 것처럼 이진탐색을 할 수 있다는 말이다.
• 그렇다면 경우를 생각해보자. 아래는 문제에서 주어진 테스트 케이스 1번이다.

  0	1	2	3	4	5	6
  4	5	6	7	0	1	2

• mid 값이 7이고 start 값은 4이고 end값은 2라고 생각하자. 이 경우에서 원래대로라면 7보다 작으면 무조건 end = mid - 1 이렇게 이동을 해야 범위가 좁혀지는데 이 경우는 7보단 작은데 4보다 큰 경우만 end = mid - 1이 되는 것이다.
• 그럼 start = mid + 1로 범위를 좁히는 경우는 어떤 경우일까? 7보다 큰 경우나 4보다 작은 경우가 될 것이다.
• 이번엔 start 값 = 7이고 mid 값 = 0 이고 end 값 = 2인 경우를 생각해보자. 자 이 경운엔 mid값보다 start 값이 크다. 원래대로라면 0보다 작은 경우 무조건 end = mid - 1이 되어야한다. 이 경우도 마찬가지로 0보단 작은 경우는 무조건 가능하다. 왜일까? start가 mid보다 더 크다라는 것은 무엇을 뜻할까? 그 뜻은 더 큰 값이 rotate해서 start 쪽으로 온 것이다. 그 뜻은 0보다 작은 놈들이 그 사이에 다 끼여있다는 것이다. 그리고 start보다 큰 값도 이 범위내에 다 있다는 의미이다. 그 이유는 rotate해서 오다 보니까 제일 처음 가장 큰 값이 아래의 범위로 오고 다음부턴 그것보다 더 작은 값들이 rotate 되기 때문이다.
• 그럼 start = mid + 1로 줄이는 경우는 무엇일까? 그건 0보다 더 크고 end보다 작거나 같은 경우이다.
• 이를 코드로 나타내면 아래와 같다.

코드구현

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        def binarySearch(arr, target, start, end):
            while start <= end:
                mid = (start + end)//2
                if arr[mid] == target: return mid 

                if arr[mid] >= arr[start]: # mid 값보다 start값이 더 작거나 같은 경우
                    if target > arr[mid] or target < arr[start]:  # mid 값보다 target 값이 더 크거나 start값보다 target값이 더 작은 경우
                        start = mid + 1
                    else: # mid값 보다 target 값이 더 작고 target 값이 start 값보다 더 크거나 같은 경우
                        end = mid - 1
                else: # mid 값보다 start값이 더 큰 경우
                    if target < arr[mid] or target >= arr[start]: # mid 값보다 target 값이 더 작거나 start값보다 target값이 더 크거나 같은 경우
                        end = mid - 1
                    else: # mid값보다 target값이 더 크고 start값보다 target값이 더 작은 경우
                        start = mid + 1
            return -1
        return binarySearch(nums, target, 0, len(nums)-1)