[ leetcode 문제풀이 ] Find Minimum in Rotated Sorted Array

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/

Find Minimum in Rotated Sorted Array - LeetCode

(Find Minimum in Rotated Sorted Array 문제는 위 링크에서 풀어보실 수 있습니다.)

 

 

 

< Find Minimum in Rotated Sorted Array 문제 설명 >

 

Find Minimum in Rotated Sorted Array 문제는 다음과 같다. 

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.

 

오름차순으로 정렬된 길이 n의 배열이 1~n 사이의 값만큼 회전하다고 하자. (예시 생략)

모두 다른 원소를 갖는 회전된 배열이 주어졌을 때 이 배열의 최소 원소를 리턴하여라. 반드시 O(log n) 내에 실행되는 알고리즘을 작성해야 한다.

 

다음 세 가지 출력 예시가 주어졌다.

 

 

주어진 제한조건은 n = nums.length, 1 ≤ n ≤ 5000, -5000 ≤ nums[i] ≤ 5000 과 nums는 서로 다른 원소로 이루어져 있고, nums 은 정렬된 후 1~n회만큼 회전되었다는 것이다.

 

 

 

---

< Find Minimum in Rotated Sorted Array 문제 접근 >

 

반드시 O(log n)내에 실행되는 알고리즘을 만들어야 한다는 것은 이진 탐색을 하라는 것이다. 그렇다면 어떻게 이진탐색을 정렬이 되다 만듯한 이 배열에 적용할 수 있을까?

 

핵심은 회전이 되었다면 어딘가 증가하다가 감소하는 부분이 생긴다는 것이다. (n회 회전된 경우 제외)그 부분을 찾아 탐색을 해주면 된다. 먼저 구현된 알고리즘을 보자. (Cpp 사용)

 

int findMin(vector<int>& nums) {
    int low = 0;
    int high = nums.size();

    while(low < high){
        int mid = (low + high) / 2;
        if(nums[low] < nums[mid])
            low = mid;
        else
            high = mid;
    }
    return nums[(low+1)%nums.size()];
}

 

nums[low] < nums[mid] 가 성립한다는 것은 nums[mid ... high] 에 minimum element가 존재한다는 것이다. 그 외의 경우(else문) nums[low ... mid]에 minimum element가 존재한다는 것이다. 

 

보통의 이진탐색과 달리 high를 nums.size()로 초기화하였다. (nums.size()는 nums의 index 밖의 범위임) 그 이유는 범위를 nums의 인덱스 내부로 제한하게 되면 mid의 몫 연산에 의해 필요한 전체 영역을 탐색하지 못하기(nums의 마지막 원소 탐색이 어려움) 때문이며 high를 nums.size()로 초기화하게 되면 n회 회전된 경우(잘 정렬된 경우) minimum element가 가상의 nums.size() index에 있는 것처럼 작동하기 때문이다.

 

또한, 위 코드의 while문을 통해 나오는 low는 minimum element의 위치가 아닌 maximum element의 위치이다. minimum element의 위치를 나타내주기 위해 low + 1 (mod nums.size())를 해주어 nums가 n회 회전된 경우(잘 정렬된 경우)도 깔끔하게 처리해주었다.