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

Leetcode 문제

이번에 풀어볼 문제는 리트코드 153번 문제 Find minimum in rotated sorted array 다.

우선 문제를 살펴보자.

 

리트코드 153번 문제 Find minimum in rotated sorted array (링크)

Find Minimum in Rotated Sorted Array - LeetCode

Find Minimum in Rotated Sorted Array - LeetCode

 

 

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

[4,5,6,7,0,1,2] if it was rotated 4 times.
[0,1,2,4,5,6,7] if it was rotated 7 times.
Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log n) time.

Example 1:
Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.

Example 2:
Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.

Example 3:
Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17] and it was rotated 4 times. 

 

 

문제 설명

문제를 간략히 살펴보자.

길이가 n인 배열이 주어진다.

이 배열안의 값들은 모두 다르며 오름차순으로 정렬되어 있다.

하지만 이 오름차순 정렬은 배열의 회전으로 인해 흐트러진 상태로 주어진다.

여기서 회전은 배열 안 값들을 1 회전 당 오른쪽으로 한 칸씩 옮기는 것을 의미한다.

예를 들어 [3, 4, 1, 2]와 같은 배열은 [1, 2, 3, 4] 배열을 2회전 한 것이다.

이때 주어진 배열의 가장 최소값을 구하는 문제다.

문제에서 주어진 중요한 제한 조건 중 하나는 time complexity가 O (log n)이어야 한다는 점이다.

이제 문제를 풀어보자.

 

 

문제 접근법

이 문제는 언뜻 보면 쉽게 풀 수 있을것 같지만 time complexity가 O (log n)이어야 한다는 조건이 달려있다.

O (log n)의 time complexity는 갖는다는 의미는 binary search를 통해 문제를 풀어야 한다는 것을 의미한다.

따라서 우리는 이 문제를 two pointers 를 이용하여 풀 수 있다.

예를 들어 문제에서 주어진 예시 1번과 같이 [3, 4, 5, 1, 2] 배열이 주어졌다고 생각해보자.

그리고 left pointer는 가장 왼쪽에 right pointer는 가장 오른쪽에 위치시키자.

그 후 두 포인터로부터 mid pointer를 정의할 수 있다.

 

 

이때 right 포인터에 위치한 숫자와 mid 포인터에 위치한 숫자를 비교해보자.

만약 배열이 [1, 2, 3, 4, 5]와 같이 오름차순으로 배열되어 있다면

right 포인터가 가리키는 숫자가 mid 포인터카 가리키는 숫자보다 항상 크다.

즉, 배열이 오름차순으로 잘 배열되어 있기 때문에 우리는 mid 포인터 왼쪽에 최소값이 있다는 것을 알 수 있다.

하지만 주어진 배열에서와 같이 right 포인터가 가리키는 숫자가 mid 포인터카 가리키는 숫자를 비교해보면

 

mid pointer (=5) > right pointer (=2)

 

mid 포인터가 가리키는 숫자가 더 크다는 것을 알 수 있다.

따라서 이 경우 우리는 최소값이 mid 포인터 오른쪽에 위치해 있다는 것을 알 수 있다.

이 과정을 반복하다보면 우리는 최소값을 찾아낼 수 있다.

 

 

문제 풀이

코드를 한 번 살펴보자.

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

그리고 left/right 포인터를 만들어 주는데 (line 2)

left 포인터는 배열 가장 왼쪽에, right 포인터는 배열 가장 오른쪽에 위치시킨다.

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

앞서 설명한대로 left, right 포인터 중간에 위치한 mid pointer를 찾아준다 (line 5)

그리고 그 mid pointer가 가리키는 숫자가 right pointer가 가리키는 숫자와 비교한다. (line 7)

만약 mid pointer가 가리키는 숫자가 더 크다면 앞서 설명한대로 최소값이 mid pointer에 오른쪽에 위치한 것이므로

left 포인터를 mid 포인터 하나 옆으로 옮겨준다 (line 8)

만약 mid pointer가가리키는 숫자가 더 크다면 최소값이 mid pointer 왼쪽에 위치한 것이기 때문에

이 경우는 right pointer를 mid 자리로 옮겨준다 (line 10)

이 과정을 반복하다보면 결국 left pointer가 가리키는 숫자가 최소값이 된다.

 

 

문제 풀이 코드

def find_min(nums):
    left, right = 0, len(nums) - 1
    
    while left < right:
        mid = left + (right - left) // 2
        print("mid= ", mid)
        print("left= ", left)
        print("right= ", right)
        print("-----------")
        if nums[mid] > nums[right]:
            left = mid + 1
        else:
            right = mid
        
    return nums[left]
 
# Test cases
nums1 = [3, 4, 5, 1, 2]
print(find_min(nums1))  # Output: 1
 
#nums2 = [4, 5, 6, 7, 0, 1, 2]
#print(find_min(nums2))  # Output: 0
 
#nums3 = [11, 13, 15, 17]
#print(find_min(nums3))  # Output: 11
 

 

이상 리트코드 153번 문제 Find minimum in rotated sorted array 문제풀이였다.

 

 

관련 문제

리트코드 1번 문제 Two sum 문제풀이

리트코드 11번 문제 Container with most water 문제풀이

리트코드 15번 문제 3Sum 문제풀이

리트코드 33번 문제 Search in rotated sorted array 문제풀이

리트코드 53번 문제 Maximum subarray 문제풀이

리트코드 121번 문제 Best time to buy and sell stock 문제풀이

리트코드 152번 문제 Maximum product subarray 문제풀이

리트코드 217번 문제 Contains duplicate 문제풀이

리트코드 238번 문제 Product of array except self 문제풀이

 

 

153. Find Minimum in Rotated Sorted Array