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

문제 링크

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

Search in Rotated Sorted Array - LeetCode

풀이

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

1. 이진탐색을 베이스로 한 2개의 함수를 작성
   1) 첫 번째 함수는 주어진 nums에서 rotated sorted pivot을 찾기 위한 함수
   2) 두 번째 함수는 일반적인 이진 탐색 함수
2. 주어진 nums 배열 속 pivot을 찾기 위해 탐색을 진행
3. 이후 pivot을 기준으로 배열을 분할하여 2번의 이진 탐색을 진행해 원하는 값(target)을 찾는다.
4. 결과에 따라 적절한 답을 반환

 문제에서 주어진 nums 배열은 일반적으로 정렬된 배열이 아닌 특정 위치를 기준으로 순환하며 정렬된 배열이다. 이렇기에 일반적인 상황으로 이진탐색은 사용이 불가능한 상태인데, 문제에선 O(logN)의 알고리즘을 요구한다. 이렇기 때문에 이진탐색을 활용해야 하기 때문에, nums 배열 속 pivot을 찾아 구간을 둘로 나눠 이진 탐색을 진행하는 방식으로 진행했다
 우선 pivot 위치를 찾는 함수를 구현한다. 결국 pivot이 중간에 속한 구간이면 해당 구간의 왼쪽과 오른쪽 값의 크기가 역순이 되어있기 때문에, 해당 조건이 만족하도록 계속 구간을 줄여 나간다. 이후 최종적으로 해당 pivot이 나오면 이를 반환하고, 만약 해당 구간이 없다면 -1을 반환하는 것으로 한다.
 이후 반환받은 pivot이 존재하는지 아닌지에 따라 로직을 나눈다. 만약 nums 배열이 일반적으로 정렬된 상태라면 바로 이진 탐색을 실시하고, 반대로 pivot이 존재한다면 이를 기준으로 구간을 나누어 이진 탐색을 진행한다. 이후 결과에 따라 적절한 답을 반환하면 된다.

 

class Solution {
    public int search(int[] nums, int target) {
        int pivot = findPivot(nums, 0, nums.length - 1);

        if (pivot == -1) {//중간에 pivot이 없는 경우
            return binarySearch(nums, target, 0, nums.length - 1);
        } else {//중간 pivot 위치
            int answer1 = binarySearch(nums, target, 0, pivot);
            int answer2 = binarySearch(nums, target, pivot + 1, nums.length - 1);

            if (answer1 == -1 && answer2 == -1) {//target이 양쪽 모두 없다면
                return -1;
            } else {//한쪽에 존재
                if (answer1 != -1) {
                    return answer1;
                } else {
                    return answer2;
                }
            }
        }
    }

    int findPivot(int[] nums, int start, int end) {//나뉘어진 pivot find
        int middle = (start + end) / 2;

        if (nums[start] > nums[middle]) {
            return findPivot(nums, start, middle);
        } else if (nums[middle] > nums[end]) {
            if (start == middle) {//start와 end가 하나 차이인 경우
                return middle;
            }

            return findPivot(nums, middle, end);
        } else {
            return -1;
        }
    }

    int binarySearch(int[] nums, int target, int start, int end) {
        if (start > end) {//못찾은 경우
            return -1;
        }

        int middle = (start + end) / 2;

        if (nums[middle] == target) {//찾은 경우
            return middle;
        } else if (nums[middle] > target) {//목표가 중앙보다 오른쪽에
            return binarySearch(nums, target, start, middle - 1);
        } else {//목표가 중앙보다 왼쪽에
            return binarySearch(nums, target, middle + 1, end);
        }
    }
}

결과