[LeetCode 해석 및 풀이] 33. Search in Rotated Sorted Array

LeetCode 문제 해석 및 풀이 방법

 

문제 33. Search in Rotated Sorted Array(한글 번역)

바로가기

 

문제 설명

영문

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.

 

한글

오름차순으로 정렬된 각기 다른 숫자로 이루어진 정수 배열 nums이 있다.

 

함수에 전달되기 전에, nums는 미지의 피벗 인덱스 k (1<= k <= nums.length)만큼 돌아갈 수 있으며 그러면 결과 배열은 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed)가 됩니다. 예를 들어, [0,1,2,4,5,6,7] 피벗 인덱스 3으로 회전할 수 있으며 그러면 [4,5,6,7,0,1,2]가 됩니다.

 

가능한 회전을 한 배열 nums와 정수 target이 주어지면, target의 값이 nums에 있다면 인덱스를, 아니면 -1를 반환하시오.

 

시간 복잡도 O(log n)로 작성하여야 합니다.

 

제한조건

• 1 <= nums.length <= 5000
• -10^4 <= nums[i] <= 10^4
• All values of nums are unique.
• nums is an ascending array that is possibly rotated.
• -10^4 <= target <= 10^4

 

입출력 예

입력	출력
nums = [4,5,6,7,0,1,2], target = 0	0
nums = [4,5,6,7,0,1,2], target = 3	-1
nums = [1], target = 0	0

 

 

해답 및 해설

파이썬 (Python)

첫 번째 풀이

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        def find_start_idx():
            # 153. Find Minimum in Rotated Sorted Array 문제에서 작성한 코드
            # 최소값 원소의 인덱스를 반환
            
        start = find_start_idx()
        if start == 0: start = len(nums)

        left = start - len(nums)
        right = start -1
        
        while left <= right:
            mid = (left+right)//2
            if nums[mid] < target:
                left = mid + 1
            elif nums[mid] > target:
                right = mid - 1
            else:
                if mid >= 0: return mid
                else: return len(nums) + mid

        return -1

153. Find Minimum in Rotated Sorted Array의 풀이로 최소값이 있는 인덱스를 구한 후, 마치 정렬된 배열인 것 처럼 취급하여 이진 탐색으로 인덱스를 구하였다. 

 

두 번째 풀이

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l=0
        r= len(nums)-1
        while l<=r:
            m = (l+r)//2
            if target == nums[m]:
                return m
            if nums[l] <= nums[m]:
                if target > nums[m] or target < nums[l]:
                    l = m+1
                else:
                    r = m-1
            else:
                if target < nums[m] or target > nums[r]:
                    r = m-1
                else:
                    l = m+1
        return -1

최소값을 찾는 과정을 따로 진행하지 않고 탐색하는 풀이