[LeetCode] 153. Find Minimum in Rotated Sorted Array

문제 출처: https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/

Find Minimum in Rotated Sorted Array - LeetCode

---

문제

오름차순으로 정렬된 크기 $n$ 배열이 $1 \sim n$번 회전되어 있다. 예를 들어, 배열 $nums=[0,1,2,3,4,5,7]$이 4번 혹은 7번 회전하였다면 다음과 같다:

• 4번 회전하였다면, [4,5,6,7,0,1,2]
• 7번 회전하였다면, [0,1,2,4,5,6,7]

 

배열 $[a[0], a[1], a[2], ..., a[n-1]]$이 1번 회전한 결과는 $[a[n-1], a[0], a[1], a[2], ..., a[n-2]]$이다.

 

정렬 및 회전되어 있으며, 구분되는 원소를 갖는 배열 $nums$가 주어질 때, 이 배열 내에서 최소 값을 찾아라.

 

단, 작성된 알고리즘은 $O(\log n)$ 이내의 시간 복잡도를 가져야 한다.

예제

Input: nums = [3,4,5,1,2]
Output: 1

Explanation: The original array was [1,2,3,4,5] rotated 3 times.

Input: nums = [11,13,15,17]
Output: 11

Explanation: The original array was [11,13,15,17] and it was rotated 4 times.

---

풀이

배열 내에서 최소 값을 찾는 기본적인 알고리즘은 반복문을 활용하여 배열 전체를 탐색하는 것으로 $O(n)$의 시간 복잡도를 갖는다. 이 방식은 문제에서 제시하는 $O(\log n)$ 보다 느린 시간 복잡도이므로, 이 방식보다 빠른 방식이 필요하다.

 

$O(\log n)$ 이라는 단서 조항이 힌트가 될 수 있다. $O(\log n)$의 시간 복잡도를 갖는 알고리즘인 이진 탐색 알고리즘을 적용할 수 있을지 생각해보자.

 

기본적인 이진 탐색 알고리즘은 정렬된 배열에서 특정 값이 존재하는지 찾는 알고리즘이다. 정렬된 배열이라는 키워드가 눈에 띄는데, 문제에서 주어지는 배열은 정렬 상태에서 회전이 되어 있기 때문에 정렬이 깨진 상태라 생각할 수 있고 이진 탐색 알고리즘의 적용이 불가능하다고 생각할 수 있다.

 

정렬된 배열이라는 키워드가 갖는 의미를 생각해보면,

 

특정 값을 찾는 문제에서 배열이 정렬되어 있다면, 임의의 기준 지점 지정하고 해당 기준 지점으로부터 찾고자 하는 값이 오른쪽에 있는지 왼쪽에 있는지 판별하기 위한 전제조건이다.

 

즉, 현재 주어진 배열에서 특정 지점을 기준으로 찾고자 하는 값이 우측에 있는지 혹은 좌측에 있는지 구분할 수 있는가? 가 이진 탐색을 이용해 문제를 풀 수 있는지 없는지를 판가름하는 기준이 되어야 한다. 아래의 그림을 보자.

위 그림은 주어지는 배열의 값을 인덱스 순서대로 좌표 평면에 그린 것이다. 위 그림에서 초록색과 빨간색으로 표시한 영역이 이진 탐색 시 범위를 특정하는 데 사용될 수 있는 지점들이다. 두 영역을 하나씩 살펴보자.

• 초록색 영역 중 한 지점이 기준점으로 선정되면, 찾고자 하는 값이 우측에 있음을 알 수 있다.
• 빨간색 영역 중 한 지점이 기준점으로 선정되면, 해당 값이 최소점 이거나 해당 값 좌측에 최솟값이 존재할 수 있다.

 

이처럼 이 문제는 특정 위치에서 내가 찾고자 하는 값이 어디에 있는지 판가름할 수 있는 문제이기 때문에 이진 탐색을 이용할 수 있는 문제이다.

 

작성할 코드의 틀을 잡아보면 다음과 같다.

var findMin = function(nums) {
    let left = 0, right = nums.length-1;
    
    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);
        
        // mid가 초록 영역에 있는지, 빨강 영역에 있는지 판단하여
        // left 또는 right 이동
    }
    
    return nums[left];
};

(코드의) $mid$ 값이 초록색 영역에 위치하는지 혹은 빨간색 영역에 있는지를 구분할 수 있는 조건은 다음과 같다.

• 초록: $nums[left] \le nums[mid]$
• 빨강: $nums[mid] < nums[right]$

 

빨강 영역에는 $=$ 케이스가 빠져있는데, 기본적으로 $mid$를 계산하는 수식 상 $right == left$ 인 케이스가 아닌 이상 $mid == right$ 인 케이스는 나오지 않는다.

 

이 조건을 활용하여 $left$와 $right$를 업데이트하면 된다.

var findMin = function(nums) {
    let left = 0, right = nums.length-1;
    
    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);
        
        if (nums[mid] >= nums[left]) {
            left = mid + 1;
        } else if (nums[mid] < nums[right]) {
            right = mid;
        }
    }
    
    return nums[left];
};

다음으로 생각해볼 건 탐색 종료 조건이다.

 

기본적으로 $left \le right$ 인 상황에서 계속해서 탐색을 해 나갈 것이지만, $left$가 빨강 영역으로 넘어가는 순간에는 멈춰야 한다. 그렇지 않으면 $left$가 $right$보다 커질 때까지 반복할 것이다. 

 

$left$가 빨강 영역으로 넘어가는 순간을 생각해보면, 기존과는 달리 $nums[left] \le nums[mid] \le nums[right]$ 의 상태가 되므로, 이 조건으로 문제의 순간을 잡아낼 수 있다. 또한 애초에 순서대로 정렬되어 있는 배열인 상황도 이 조건으로 잡아 낼 수 있다. 

var findMin = function(nums) {
    let left = 0, right = nums.length-1;
    
    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);
        
        if (nums[left] <= nums[mid] && nums[mid] <= nums[right]) {
            break;
        }
        
        if (nums[mid] >= nums[left]) {
            left = mid + 1;
        } else if (nums[mid] < nums[right]) {
            right = mid;
        }
    }
    
    return nums[left];
};

 

Github: 153.js

GitHub - opwe37/Algorithm-Study