LeetCode: 81번 (Search in Rotated Sorted Array II) [JAVA]

문제 링크

https://leetcode.com/problems/search-in-rotated-sorted-array-ii/

Search in Rotated Sorted Array II - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

1. 우선 반복문을 통해 nums 배열을 돌며, 구간이 분리되는 pivot을 찾음
2. 이후 pivot의 결과에 따라, 구간을 하나 혹은 두 개로 분리하여 이진탐색을 진행
3. 탐색 결과 반환

 이전에 풀었던 33. Search in Rotated Sorted Array와 유사한 문제이다. 다만 이전에 해결한 문제의 경우, 주어진 nums배열 속 요소들이 모두 유니크하기 때문에, 구간이 나누어지는 pivot을 찾는데 이진탐색을 활용할 수 있었다. 하지만 이번 문제에선 주어진 nums 배열에 요소들이 유니크하지 않기 때문에, pivot을 찾는데 이진탐색을 활용하는 경우 구간이 제대로 찾아지지 않는 문제가 발생한다.
 결과적으로 분리된 구간을 찾게 되면 이후에는 그 구간에 맞게 이진탐색을 진행하면 되지만, 이번 문제에서는 크게 pivot을 찾을 방도가 보이지 않다보니, 결국 단순 for문을 통해 pivot을 찾는 것으로 진행했다. 결국 주어진 nums 배열을 한 번 돌며 pivot을 찾아 break를 한다. 이후 만약 pivot이 없다면 전체 구간에 대해 이진 탐색을 진행하고, 만약 pivot이 있다면 해당 값을 기준으로 구간을 나누어 두 번의 이진탐색을 진행한다. 이후 해당 탐색 결과를 반환하면 된다.

 

class Solution_LeetCode_81_Search_in_Rotated_Sorted_Array_II {
    public boolean search(int[] nums, int target) {
        int pivot = -1;

        for (int i = 0; i < nums.length - 1; i++) {//앞에서부터 탐색하며 pivot 위치 탐색
            if (nums[i] > nums[i + 1]) {
                pivot = i;
                break;
            }
        }

        if (pivot == -1) {//pivot이 없다면
            return binarySearch(nums, target, 0, nums.length - 1);
        } else {
            return binarySearch(nums, target, 0, pivot) ||
                    binarySearch(nums, target, pivot + 1, nums.length - 1);
        }
    }

    boolean binarySearch(int[] nums, int target, int start, int end) {//재귀 기반 이진 탐색
        if (start > end) {
            return false;
        }

        int mid = (start + end) / 2;

        if (nums[mid] == target) {
            return true;
        } else if (nums[mid] > target) {
            return binarySearch(nums, target, start, mid - 1);
        } else {
            return binarySearch(nums, target, mid + 1, end);
        }
    }
}

결과