[LeetCode/Hard] 154. Find Minimum in Rotated Sorted Array II (JAVA)

문제

---

선형탐색 풀이

카테고리는 이분탐색이었지만, 이분탐색으로 접근하기 전에 O(N)의 시간복잡도로 풀 방법이 떠올라서 그렇게 먼저 문제에 접근을 해봤다.

랜덤으로 숫자들이 섞이는 게 아니라 rotate 된 것이기 때문에, 몇 번 rotate 하던지간에 특정 인덱스 k를 기준으로 왼쪽과 오른쪽이 각각의 오름차순 배열이 된다. arr[0]부터 arr[k-1]까지 하나의 오름차순 배열이고, arr[k]부터 arr[n-1]까지 또 다른 오름차순 배열을 형성한다는 것이다. 그래서, 그 k만 찾아서 arr[0]과 arr[k] 중 더 작은 값을 답으로 리턴하면 된다.

k를 찾는 방법은 그냥 arr[i-1]과 arr[i]을 비교했을 때 오른쪽 인덱스인 arr[i]가 더 작으면 그 i가 새로운 오름차순 배열의 시작이라는 뜻이라서, i가 k가 된다.

예외 가능성을 생각해본 것은,
1. n번 rotate 되어서 모든 원소가 하나의 배열로 오름차순 정렬되어 있는 경우
2. 모든 원소가 같은 수인 경우
이렇게 두 가지인데, 두 경우 모두 본 알고리즘의 worst case에 해당할 뿐, 익셉션이 뜨지는 않는다. 두 경우 모두 k에 i가 배정이 되는 일이 없어서, 초깃값인 0가 k의 최종값이 된다. 그래서 결국 nums[0]을 반환하게 되어 정답이다.

코드

class Solution {
    public int findMin(int[] nums) {
        int k = 0;
        int before, current;
        for (int i=1 ; i<nums.length ; i++) {
            before = nums[i-1];
            current = nums[i];
            if (before > current) {
                k = i;
                break;
            }
        }
        return Math.min(nums[0], nums[k]);

    }
}

---

이분탐색 풀이

하지만 문제의 의도가 이분 탐색으로 이 문제에 접근하라는 것이었으니.. 추가로 고민을 해봤다.

left, mid, right 세 인덱스의 값을 비교해서 인덱스를 조정해가면서 최솟값을 찾기 위해 경우의 수를 나눴다.

1. arr[left] < arr[right] return arr[left];
2. arr[left] > arr[right] left++;
3. arr[left] < arr[mid] left++;
4. arr[left] > arr[mid] left++;
5. arr[mid] < arr[right] right = mid;
6. arr[mid] > arr[right] left = mid+1;

이를 바탕으로 코드를 작성하면 아래와 같다.

코드

class Solution {
    public int findMin(int[] nums) {
        int left = 0, right = nums.length-1, mid;
        
        while (left < right) {
            if (nums[left] < nums[right]) return nums[left];
            
            mid = (left + right) / 2;
            if (nums[mid] < nums[right]) right = mid;
            else if (nums[mid] > nums[right]) left = mid+1;
            else left++;
	}
	return nums[left];
    }
}